Having done this on 2 continents now.
Go through other peoples wedding photos online, and find out what shots/styles you like don't like.
Collect examples of the photos you like. Find a photographer you like. Show the photos to the photographer and discuss.
My other half had a list of specific shots she wanted. She made a list, and we went through it with the photographers and made sure she got them. She wanted photos of her getting ready in the morning etc.
You can always say to a photographer, I like your work, I really want to use you, but you're slightly out of my budget, and see what they say.
One thing you may want to consider is asking your guests not to use cameras/camera phones, as you may get a lot of official photos of your guests taking photos of you.
The in laws wanted a video, it was out of our budget,so they paid for the video. It's actually our favourite memento of the day. well the trailer is, can't bring myself to watch the full video yet.