A wireless hotspot enables a computer to serve as a router over Wi-Fi. Ubuntu lets you easily create a wireless hotspot by using the Network Manager, but it uses an ad hoc network and most Android and Windows Phone devices can’t connect to such networks.

For this reason, I’ve created (in collaboration with Satya) a script called AP-Hotspot that automatically creates an infrastructure (Access Point mode) wireless hotspot in Ubuntu that should work with Android and Windows Phone devices. The script uses hostapd and dnsmasq and it requires Access Point mode support for your wireless card – AP-Hotspot checks for this automatically and won’t run if your wireless card doesn’t support it.

Full article:
How To Set Up A Wireless Hotspot (Access Point Mode) That Supports Android In Ubuntu (Linux A.I)
Alternate location of above article (WebUpd8)

If you don’t feel comfortable running a script, the script is based on these instructions, so if you want you can do it manually:

[GUIDE] Making infrastructure wifi hotspot on ubuntu 12.04/12.10 (xda developers)