How to make a reservation in Japanese

I want to make a reservation at a shokubo and want to be sure I am using the correct words in Japanese. Can someone help with a translation? "I would like to make a reservation for two people on May 13 for one night. Do you have a room available on that night? We will arrive around 3 PM." Do I first say Onegai shimasu...

Hi Otsuki, I'll try to translate this for you:

五月庶O日に二人で一泊よやくして下さい。その夜にひまな部屋がありますか。午後三時ごろ着きます。

go gatsu juusan nichi ni futari de ichi haku yoyaku shite kudasai. sono yoru ni himana heya ga arimasuka? gogo san ji goro tsukimasu.

This directly translates to "On May 13th, can I please make a reservation for two people for one night? Do you have a room free on this night? We will arrive around 3pm.

This probably isn't the best conversation you could have, so it is probably best for someone else to clarify the finer points, but overall I think it is what you are after. Good luck!

- Yoyaku wo onegai shimasu. (I would like to make a reservation.)

They would probably ask when ... you might hear something like: "itsu desu ka?" "Itsu deshou ka?" (When do you want it? Listen out for "itsu" = "when")

Then you can say:
- Go-gatsu juusan-nichi ni, futari de ippaku desu. (It will be on May 13th, one night stay for two people.)

- Heya wa aite imasu ka. (Do you have a vacancy?)

If yes, they will ask for your name... then later, to say you will arrive around 3 pm:
- Gogo san-ji goro tsukimasu. (Will arrive around 3pm.)

Note to chompalomp2,
"hima na" is used to describe people having free time on their hands, or days going at a leisurely pace, not for "vacancy," just for your information.

Thank you both chompalomp2 and AK. I wanted to be sure to be polite and use the correct words. This was a great help.