I am using an Arduino Duemilanove and an EM-406A GPS module.
NOTE: The breadboard is not necessary but makes the job a lot easier.
Step 1: Customizing the GPS
Cut the connecting plug of the furthest side of the GPS' connection wires.
Now it is your choice to extend them with longer wires, make sure to connect them thoroughly.
Remove the plastic off the ends of the wires.
See the images below.