should work with the arduino. just figure out which pins are rx, tx,power, ground. make sure you use the same baudrate so you can see the nmea data. theres alot of gps tutorials on the net. check www.adafruit.com go to tutorials and then go to gps shield. lots of good info there. www.sparkfun.com has a write up on their site last i checked. im using the newer surf 3 unit with my gps i built with arduino.i used the new soft serial library, tiny gps library. i posted my code on the forums here bur im interfacing the serial.print to lcd.print.
I have just tried the TinyGps and NewSoftSerial, but it dont show anything, and i have read that the Tinygps software might have problems with Arduino Megas.