By default, VirtualBox OSE when installed from apt in Ubuntu uses its own internal DHCP server and is segregated from your LAN.  This may not be an issue if all you need to access is the Internet, but if you need to access other machines on your network from it or access it from other machines on your network, you'll need to setup a bridge.  There are bits and peices of how to do this on the Ubuntu forums but I'm gonna lay it all out right here and tell you exactly what to do.

First, you'll need to setup a tun/tap interface in the Ubuntu host.  We do that with the following commands:

sudo tunctl -t tap1 -u yourusername
sudo brctl addbr br0
sudo ifconfig eth0 0.0.0.0 promisc
sudo brctl addif br0 eth0
sudo dhclient br0
sudo brctl addif br0 tap1
sudo ifconfig tap1 up
sudo chmod 0666 /dev/net/tun

We now have a new network interface called tap1.  In VirtualBox, open your settings for whatever guest you're setting up and go to the Network section.  Set "Attached to" to Host Interface and set the Interface Name to tap1.

That's it.  You're done.  Now your guest operating system will get its IP from your DHCP server.  If for some reason, you're not using a DHCP server, all you have to do is replace the line

sudo dhclient br0

With

sudo ifconfig br0 youripaddress

To have the tap interface automatically start every time you boot, you can setup an init script.

#/bin/bash

tunctl -t tap1 -u yourusername
brctl addbr br0
ifconfig eth0 0.0.0.0 promisc
brctl addif br0 eth0
dhclient br0
brctl addif br0 tap1
ifconfig tap1 up
chmod 0666 /dev/net/tun

Stick that in /etc/init.d and save it as vbox-networking or something to that effect and chmod +x it.  It will then run every time your computer boots and you won't have to worry about it anymore.  I'm using certain interfaces here like eth0, br0, tap1, etc., but you may have to change these depending on your system.  eth0 is the nic that's connected to the network, br0 is the first bridge I have set up, tap1 is the first tap I have set up.  You can change all these to suit your configuration.

Note:  This is true with Ubuntu, but it should be completely portable with any other distribution.