iz "az ő" part necessary or can it be omitted
I believe you can omit the 'ő', but you do need the 'az'.
That's correct. :)
isn't it "his bed" because of the "ő"?
It's "their bed" because of the -uk ending. If you use a pronoun in the possessive construction, 3rd person singular and plural both use ő. So az ő ágya is his bed and az ő ágyuk is their bed.
Unless their a couple, I would expect "Where are their beds?".
Greg, that's also a good translation.