Have you read the Ubuntu documentation on Internet Connection Sharing?
This assumes that your ethernet port (where the XBox is connected) is eth0:
- Go to "System" on your top bar
- Navigate to "Preferences" and select "Network Connections"
- When that window opens, select "Auto eth0" and press "Edit" (This assumes that you are connected to the internet on some other port, for ex. wlan0 using wireless)
A new window will open. Navigate to the tab titled "IPv4 Settings" and change the Method to "Shared to other computers". After restarting the computer you should now be able to plug in any computer into your other Ethernet port or share through your wireless card.
So to adapt this, you will need the USB internet connection, but you said you got this working.
I believe the XBox will fetch the IP address automatically. If not you will have to set it so it is in the same subnet of your eth0 but using another IP address. Its gateway will be the IP address of your Ubuntu laptop.
There's also a HOWTO with screenshots for Ubuntu 9.10.