If neither of you have ridden a freestyle yet, I would strongly suggest that you consider holding off for a year on the Pas de Deux, and each do a freestyle first. The recommendations that others made above about measuring the beats per minute of your horses gaits, and then choosing music that fits exactly is good advice. If you want to go that route, the website that is really helpful with this is: http://www.equimusic.com/
That is not the only way to go. Sometimes you can find music that is suggestive of the gait and fits well with your horse even if the footfalls are not exactly on the beat. Either way: Videotape your horse at the walk, trot, and canter - then watch the video with the music playing and select music that you think goes well with your horse and enhances the movement. (using the samples on I-tunes works well for this). You will want to choose 3 different pieces - one for walk, one for trot, and one for canter. Once you have selected a few possibilities, ride your horse with the selections playing and see if there is one that seems to “fit” better - you will often get a feeling while riding to music about whether the beat fits the horse. Also, some sound-sensitive horses dislike certain types of music, so this is a good time to check for that - remember it will be playing fairly loud during your performance. Not just “background” music.
Next make your choreography. As previously recommended, video your horse doing the choreography. You can then time how long the music should be for each section. OR if you like video editing, you can just use the selected music to make a soundtrack to the video, then edit it right on the video editing software. You will find that need to make sections of the choreography a little bit longer or shorter in order to make the editing breaks at a pleasing placed in the music (i.e. beginning and ending of a musical phrase). You don’t need to have special music for every single movement, but do try to place stronger parts of the music where you do your lengthenings, etc.
Remember that it is not important that your movements or transitions happen right at a letter. It is OK to cut off one end of the arena, or to make a transition between letters. However, if a circle is a required movement, it needs to be exactly the right size, and anything that happens on the centerline should be right on centerline.
Then listen to the edited music many times until you know it well. Then ride your choreography to it until you can reliably get the transitions and movements timed to the music.
Yes, there are people (professionals) who will do all of this for you. One of the most fun, and effective ways to get a pro to do this, is at a “Freestyle Clinic.” – Check with GMO’s and trainers in your area to see if one is scheduled anywhere near you. Usually at a clinic, the presenter works with you one day on selecting music that you like and which matches your horse well. Then on day two, she works on choreography. She will help you work out choreography that show-cases your horse’s strongest movements and hides his flaws, but still fulfills all of the requirements. Then she either times you doing the movements, or videos you so that she can edit your music and give you a finished product. The cost of doing it this way can be anywhere from $300 - $1000 depending on the clinician. Two of the most popular are Karen Robinson, and Cynthia Collins. They both have excellent websites that explain what they do. If you can’t get to a clinic, either of them will also work with you through e-mail and sending video/music back and forth to do the same thing long-distance. Even if you decide that you want to do-it-yourself, auditing a clinic can be VERY helpful for ideas and for understanding the process.
There are also other people who will sell pre-made music and choreography for less money. These are not specifically made for your horse, but are just timed for an “average” horse. You tell the pro what size horse you have, what genre of music you like, and they send you edited music and written choreography. These are less expensive, and easier. They are actually quite acceptable for lower level competition, but IMO not as satisfying, and don’t help you to learn about what the process of what dancing with your horse is supposed to be about. (sorry, I don’t know any names off the top of my head, but you should be able to find some with a google search.)
When you get to actually doing the Pas de Deux, it won’t be so important that the beat of the music exactly matches your horse, because most of the time, the horses won’t exactly match each other anyway. (But there are a couple really well matched pairs out there who actually do stay in step.) However, you will still want to watch each horse (separately) going with the possible musics and pick some that seem well matched to BOTH horses and enhance their gaits.
Also look at youtube videos. If you search for “Dressage Freestyle XXX Level” or “dressage pas de deux” you will find lots of examples that will be helpful for ideas.