It still holds true that the verb comes at the end of the sentence, but you have to create what is known as an embedded sentence. You put one sentence inside another.
So, for your example "I didn't know how to eat with chopsticks until yesterday"
you can view "I didn't know ( )" as one sentence with the thing you didn't know in the (). In this case though, rather than one word it is an entire sentence in the (). That sentence being "how to eat with chopsticks until yesterday".
The Japanese would then become something like 昨日まで箸をどうやって使ったらいいか分かりませんでした。
Actually this particular example would really only need one verb in Japanese, 昨日まで箸の使い方が分かりませんでした。 since 使い方 is technically a single noun here. This way is more natural I think but I tried to keep two verbs in the translation above.
Anyway, 昨日まで箸をどうやって使ったらいいか is a whole sentence in and of itself, then you tack on the other verb after the first verb (which has to be in plain form).
As for your second example, I've created a bit more complicated embedded sentence
箸がやってくるまで Until chopsticks were invented (came about)
何が使われた What was used
のでしょうか sort of wraps the whole sentence together.
So a sort of literal translation would be something like "What do you think / I wonder what was used before they invented chopsticks."
Embedded sentences are created often with の / こと and と
The の and こと basically turn the verbs they are attached to into a noun so you can attach another verb to that as normal.
と can be used when quoting something as well as some other cases.