I want to purchase this new GPS on sparkfun, but I have no idea how to get the correct supply voltage (1.8vdc) for it from the Arduino.
That module requires 65 mA max. A linear regulator from the 5V supply would only dissipate 210 mW. That's low enough that no heat sink is required. While there are more efficient and fancy ways, if you have to ask here this is probably the better solution since it's simple.
If the Arduino has a 3.3V supply that can spare a extra 65 mA, even better. That would mean the 1.8V regulator would only drop 1.5V, for a dissipation of 100 mW. Make sure you put a 1 µF or so ceramic cap immediately in front of and after the regulator.
If you are stuck with 5V in, then you can use a dropping resistor on the input of the regulator to split up the dissipation between the regulator and the resistor. Let's say whatever LDO you get should have at least 1V headroom. That means you need 1.8V + 1.0V = 2.8V after the resistor, and the resistor can drop up to 5.0V - 2.8V = 2.2V. From Ohm's law, 2.2V / 65mA = 34Ω, so the standard value of 33Ω in series with the regulator will work fine. Again, don't forget the ceramic caps on the input and output of the regulator. The input cap is especially important with the dropping resistor.
Here is the circuit I was talking about:
At the maximum current of 65 mA, the resistor drops 33Ω x 65mA = 2.1V and will dissipate 140 mW. The regulator will drop the remaining voltage of 1.1V and will dissipate 70 mW. 140 mW dissipation in the resistor is enough that you need at least a 1206, although check the specs. A "1/4 W" thru hole resistor will work fine for this.
You would need a voltage regulator. They are typically simple 3 terminal devices that take a higher supply voltage as an input and outputs a lower voltage for supply to other components. They come in a few varieties, the main two categories are linear and switching regulators, and then underneath those, fixed and adjustable regulators.
Adjustable regulators can be configured to output a voltage within a range using a resistor configuration. Fixed voltage regulators only output one voltage level that they were designed to output.
For your case, a simple fixed, linear regulator like so would work well: http://search.digikey.com/us/en/products/MCP1700-1802E%2FTO/MCP1700-1802E%2FTO-ND/652675
Take a look at the datasheet on how to hook it up, they usually need smoothing capacitors in the micro-farad range on their input and outputs. Some caveats: be aware of the maximum current draw that they can handle (they will start to drop in voltage if you draw too much) and the minimum input voltage required to get a stable output voltage.
If you can't find a fixed 1.8V voltage regulator conveniently, a variably adjusted one can be adjusted for 1.8V output (given that you get one that has 1.8V in its range).