The first step is to find a suitable GPS device. There are many choices, but what you are looking for is a GPS device that can communicate via a bus that is available on Arduino. One possible device is VPN1513 GPS Receiver w/ Antenna, marketed by Parallax and available on their online store, www.parallax.com. The following is an image of the device:

Fortunately, this unit comes with its very own antenna, and you'll connect this to the RF (gold) connector on the board. This particular device interfaces using the I2C interface, one that your Arduino supports. In order to connect the device, you connect the pins to the board. The following is an image of these pins:

You'll connect your Arduino using the following connections:

Now that the two devices are connected, you can access the device via the Arduino IDE.