In Windows;

Open network connections > right click the adapter that is connected to the internet** > select properties > (vista: click sharing) XP: click Advanced > Check the check box that says "Allow other users to connect through this computer's Internet connection" > click Okay

**this cannot be the same as the wireless adapter you are going to share the internet over**

Now to connect your other "non internet" machine to the internet enable machine's wifi via an adhoc network.

Click Start > Control Panel > Network and Internet Connections > Network Connections > Right-click your wireless network connection > Properties > Wireless Networks tab > under Preferred networks click Add
>
In the Wireless network properties dialog box, on the Association tab, type the name of your wireless network in Network name (SSID) box. Choose Open for Authentication and None for encryption (not a necessity just makes it simple in this explanation)
>
Click OK.
>
Click OK again to save your changes.

Now go to your other computer and connect to the network name you just set up!

When you are asking "How do I share my internet connection over wifi" are you referring to linking the two computers together using wifi while one computer is connected to wired connection? Or are you assuming you want to use the wifi on the primary computer as a relay for the secondary?

The first is doable using Internet Connection Sharing. The second is not doable without another wifi card in the primary computer. To utilize ICS and do a wifi to wifi connection, then routing the traffic over the wired connection you'll create an ad-hoc network between the two computers and enable ICS on the wired connection. Should be pretty straight forward using the Windows help center with out to do both things (i.e. do a help search for ad-hoc wireless network to set that up and then do a help search for Internet Connection Sharing for a walkthrough on how to set the ICS up).

Visual Example:
[Router] ---- wired connection ---- [PC1] o)) wireless connection ((o [PC2]

In order for the connection to be "bounced" (the second scenario), you'd use a second wifi card and use THAT as the ICS'd connection to the wireless router while using the first card to establish an ad-hoc wireless network with the other wireless device.

Visual Example:
[Router] o)) wireless connection ((o [PC1] o)) wireless connection ((o [PC2]

In essence the second scenario is the same as the first; however, the ICS connection is now wireless instead of wired.

Hope that helps.
Take care.

Windows is easy, all you need is a router, internet connection of course, modem and ethernet cable.

Windows has its own configuations system, called Network Manager. I dont reccomend using the one that comes with your router.

Routers I reccomend are, Belkin and Linksys.

Modem will come with your ISP.

--
Linux is another story, first I would need to know what Distro you are running, Debian, Fedora, Ubuntu etc.

You can share wifi connection over network but the only thing you will require is Wireless network card for each computer you share:

Step 1
Set up a broadband Internet account through a cable or DSL Internet provider if you do not already have one in place. The higher bandwidth you can get in your Internet account, the faster the Internet connections will be in your household (given that the bandwidth will be shared among multiple computers). Make sure that connection sharing is allowed under the terms of your account, also. Some Internet service providers have a user agreement that states that specific account types can only be used on one computer.
Step 2
Test your Internet connection by connecting it directly to one of your computers (if it is a new account). You will want to make sure that the modem is working properly and that the account is active before you start trying to set up your wireless network.
Step 3
Verify that each computer that will be sharing the connection is equipped with a wireless access card. In newer machines, it is likely that a wireless access card will already be installed in the computer, but if you have an older machine you may need to buy a wireless card. If you don't have room in your machine to install a wireless card, it is possible to use a USB plug-in wireless access device. Any new device that you install in a computer may require a driver, which should come with the product but can sometimes be downloaded off the Internet.
Step 4
Connect your DSL or cable modem to a wireless router. Follow the instructions that came with the wireless router to configure the router. There may be a CD-ROM disc that you will need to install into one of your computers in order to access the router, or you may need to type a specific IP address into the browser of one of your computers with a functioning wireless access card. During configuration of your router, you may need to enter information such as the account name and password for your Internet account and the type of wireless encryption you wish to use.
Step 5
Open the configuration software for the wireless networking card or access the Internet networking controls in each computer that needs to share the connection. Select that you are using a wireless access network, and enter the configuration information in order to access your router, such as the network name and the wireless password if you included encryption when you were setting up your router.
Step 6
Test to see if your newly configured computer is able to access the Internet, and troubleshoot as needed. You may have made a typo in your wireless password or forgotten to select a specific option during the configuration. If you cannot get your computer to access the Internet, call the technical support line for the vendor of your network card or wireless router.