I did this yesterday, so it's fresh on my mind. :)
First, for your wires and whatnot, I highly recommend monoprice.com. Excellent products, and very affordable. I also found an excellent, power-saving 8-port 1Gbps switch on Amazon.
In a best-case scenario, you'd want to run the wires across the attic/crawlspace and then down/up into the walls. If there's any way to access over your head or below your feet, that's the way to go. In that case, interior walls are easy to get to, just aim right when drilling down! This is by far the best solution, since the only drywall disturbed is where you install the jack.
But as for exterior walls--forget about ceiling access, the combination of tight working spaces, insulation, etc. will make it impractical to do without opening the drywall and running across the wall. And in most cases, floor access will be just as hard.
For that scenario (across the wall), you'd need to open a small section of drywall (perhaps 3"x8" across each stud, and use a drill with a LONG bit to get through the studs at an angle. Then, like a ceiling-down or crawlspace-up installation, use a fish tape to pull the wire through.
You'll need about a 5/8" hole or so through the studs to get a CAT6 cable with the RJ-45 end on it through the hole. You can go a lot smaller for just the wire, but I recommend buying cables with the RJ-45 connector molded on--proper punch-down for CAT6 leaves a lot less room for error than 5 or 5e, and MonoPrice and others sell an excellent Keystone-style coupler so the wall-plate still has an RJ-45 jack, not a wire coming out of the wall.
Another option for across-the-wall installation is to run the wiring behind the shoe molding or the baseboards. Then, your run up to the jack can either be behind the wall (a short run that you should be able to fish relatively easily) or just up the wall (home improvement stores have cable channels to help tidy this up).
A third option for exterior walls is to run it in conduit on the outside of the home. Aesthetically, this is the worst option, but if the conduit is hidden by bushes or something where you need to go through the wall, it may be a viable option.
For jacks, I recommend a Keystone-type system combined with a low-voltage (orange and backless at Home Depot) old-construction electrical box. This combination offers the best flexibility for the future and easiest cable management (making the turns) inside the wall.
If you have thick plaster walls or shiplap behind drywall (common in older homes), skip the low-voltage box, you'll need deep, blue plastic boxes for old construction, and replace the screws that hold the wings with longer versions of the same, since those screws are only long enough for 5/8" drywall.
Always run two wires. One for what you're doing right now, and another (just a strong, loose wire without connectors) so you can pull something else through in the future easily without opening up the walls again.
Be generous with taping. It's always easier to remove electrical tape that is holding your fish tape to the wire you're pulling than it is to try to retrieve said wire if it come detached from the fish tape during the pull.