(updated to first priority oct. 2015) It is impossible to avoid mentioning the ESP8266 wifi module. There is so much going on now with that chip that your best bet is visiting ESP8266 forum and/or to google it. There is even arduino support for its on-chip processor.
(updated feb 2016) SeeedStudio and MediaTek LinkIt Smart 7688/7681 is a low-cost, low-power consumption component for IoT devices. The module integrates the MediaTek MT7681, which supports single stream IEEE 802.11b/g/n, provides GPIO and PWM for intelligent control and a UART interface for device communication.
(pre-oct 2015 priority list):
The CC3000 based board from adafruit at $35 looks promising. It contains 3.3V regulator that can handle the 350mA peak current, and a level shifter to allow 3 or 5V logic level. Can be had with internal or external antenna. Dimensions: 26.22mm 40.45mm x 2.95mm (1.03″ x 1.59″ x 0.11″). A quick test with arduino has been done by i.e. openhomeautomation. Recently the improved CC3200 that includes an integrated microcontroller.
I’ve also seen a CC3000 board sold on Tindie by BBTech. Dimensions: 30mm x 20mm (1.18″ x 0.8″). According to the question tab on that page there is arduino software available, only via email (whatever that means…). Cheaper ($23) than Adafruit, but is only 3.3V and internal antenna.
EMW3165 – Cortex-M4 based WiFi SoC Module might compete with 8266.
Seeedstudio sells Black Widow, an Arduino Duemilanove compatible clone that has 802.11b wireless connectivity baked directly onto the board.
Sweet Pea LeoFi is an Arduino Leonardo compatible board with an integrated Wifi module.
Sparkfun has WiFly RN-171.
Elecfreaks has WizFi210.
Or what about the WiDo from dfrobot.com, an Arduino compatible WIFI IoT Node development board with ATmega32u4 and WG1300 WIFI solution integrated on one board.
mt7688 or mt7681 from MediaTek.
There is also the Arduino Yun or even the Yun shield.
The “official” arduino presents an alternative solution based on HDG104 Wireless LAN 802.11b/g System in-Package. I can use that as a prototype but it does not satisfy my requirement for small size.
I’ve also read that some people buy off-the-shelf wifi routers and updates it with new software. Here is one example using a TL-WR702N. It can be bought in Norway at apprx. 200 NOK. It’s probably even cheaper other places.