As an addition to Tom's post: I've used the CC3000 but I'm driving it myself. It's a little complex and real power hungry (spikes of +300mA) but I've been made use it rather than my chosen chip, the CC1110. Groan...
However, Adafruit have a lovely little CC3000 based module and they have code for the Arduino (and thus ATMega) that worked very nicely when I tried it last year. I had no issues whatsoever but then I was using Adafruit's work to help me. Use them, they're great.
I've used raw WiFi chipsets (LSR TiWi). These are chipsets that require a Linux or Windows machine behind them (I was using an ARM Cortex A8 embedded system) to provide the communications (TCP/IP and all the rest Tom describes) stacks. The LSR connects via 25MHz 4 bit SDIO so a bit of a journey from an ATMega.
I hear lots about the ESP8266. It's terrifyingly cheap and thus worth a shot regardless of how well it works for you. At that price point, all sorts of hobbyists and professionals are leaping on and producing lots of examples and docs. Adafruit sell them now. Note that its a 3.3V module, not 5V. The ESP8266 uses an "AT command" style of serial interface. So you can do something like this:
AT+CWJAP="WiFiAccessPoint","MyPassword"
to join an access point. And
AT+CIPSTART=4,"TCP","google.com",80
to create a TCP connection to google on port 80 using channel #4. It's all pretty cool actually!