Getting a tiny bit confused about where to put the verb. Why not at the end here?
Typically the verb goes last in declarative statements, but not always.
Typically the verb goes much earlier (first or second) in questions.
At the end: the more common, but at any other place, it's right too.
Isn't "Ubi puellae sunt" correct as well?
Yes, it is.
Wouldn't 'sunt' become 'suntne' as it is a question?
It can either be a yes-no question or it can be a WH-question. It can't be both. Here, the question word is "ubi". You can't also have "-ne".