How do I install a new exterior GFI outlet?
You have a fairly simple project.  Assuming you intend to tap the interior outlet for power, here are the steps and materials: 


First, check that you have enough room in the interior outlet box to introduce one new piece of 14/2 or 12/2 NM, whichever is the same size as in the box now. I will assume you know how to make a parallel electrical junction in the interior box.
Next, run that short piece of wire
through a clamp in that box,
across/through the wall cavity and
out of a 1/2 to 3/4 inch hole in the
exterior wall close by. I don't know
what kind of siding you have, so I
can't tell you exactly how to make
the hole, but a spade type wood bit
works well on many types of
material.   Minor fishing of the
cable will be required, but not
difficult, especially if the
interior box can be removed
partially to improve
visibility.
Once you have fished the wire from inside the interior box to the exterior, made your interior electrical connections and secured the cable inside, caulk the  exterior hole around the wire with silicon.
Feed the wire into an exterior surface mounted box using the proper grommeted fitting. Caulk around the back edges of the exterior box with silicone (to make the back water tight) and fasten it to the wall.
Now you can connect your new GFIC outlet and install your weatherproof cover.


Of course, use proper safety procedures: turn off power at breaker panel before working in the interior box and doing any wire connections.  BTW, if you have vinyl siding, there are special exterior boxes that will fit nicely. These are available anywhere.  I know this is a long answer and maybe a bit confusing, but it is really a simple task.  Good Luck