Essentially you want to turn your (Ubuntu) Linux laptop into an access point router. This may not always possible given the type of wireless chipset in your laptop. See http://linuxwireless.org/en/users/Drivers. (The site pointed out by chunkyb2002 focuses around providing routing services using physical media, i.e., multiple ethernet)
Anyway, a stupid question, but have you've already considered purchasing a normal wifi router and plugging it directly into your incoming internet connection?
If you have ruled this out, was it because your ISP restricts connection by MAC address? .. Most entry-level routers (Linksys/Cisco I know can) allow you emulate an existing MAC address to fool ISPs into providing a connection. Simply configure it to the same MAC address of your laptop, then your ISP will think its your laptop connecting, and be completely unaware of the NAT-hidden clients behind the router.
Let's say for whatever reason this too isn't possible. You could purchase a secondary USB/ethernet adapter and plug that into the aformentioned wireless router's WAN connection, and then follow the directions provided by chunkyb2002. This does over-complicate the solution though, as you'd be adding NAT unnecessarily between the linux host and your smartphone through the router (the later would be able to access the former directly, but not vice versa.)
Finally, as a last resort, most smartphones do support Bluetooth. Ubuntu would support sharing a bluetooth connection as a network interface. Even if your laptop lacks bluetooth support, there are many bluetooth usb adapters available, but stay away from D-Link due to proprietary firmware ;)
Good luck!
