What is the cheapest way to add wifi to Arduino?

Some months have passed since my previous answer and now the ESP8266 based WiFi modules are available.

They get connected to your project serially (3.3V) and are controlled in a modem like way using AT commands.

With a pricing of round about $5 they fit the question better than my previous OpenWrt based answer.

For more information about ESP8266 ask your favorite finding machine or list news with tag ESP8266 at Hackaday.

---

(Old answer from the pre-ESP8266-days:)

I vote for a small router reflashed with OpenWrt like "TP-Link TL-WR703N".

It is like building an own Yùn with an Arduino of your choice...

The WR703N:

It has Ethernet, 150MBit WiFi, USB and if you want to solder, a serial console and 2 GPIO-Pins which can be turned into I2C.

This sure is not a chip- or stamp-sized solution but often cheaper than the alternatives, more powerfull and extendable.

Search the net with your favourite find'o'bot for "arduino wr703n" and you'll find lots of examples...