There could be several problems, so I'll give you some hints and hope to push you in the right direction. If that doesn't do it, post some more specific info about the exact nature of your set-up and ask again.
What you probably have as your interface to the internet is a box that acts like a router and has various ervices enabled (is it wired or wireless?). In particular dhcp and some variant of bonjour (avahi).
From dhcp (the server), the box will hand out ip adresses (eg 192.168.1.x) so that if your computer has the client part of the process running, you won't have to do anything much to get an address on the correct sub-net to work with your interface box. If you don't have the client part running on your computer, this won't work, so check this.
(It is actually not difficult to work around this manually, if needs must. If you know the 'most significant' part of the ip address (the 192.168.1 part in the example above) used on your network, then you only have to choose an unused address in that range... you would probably want to avoid x.x.x.0 or .1 and .254 and .255 even if you can't see anything using them. You could use, eg, wireshark to see the traffic on your network, but you may think that this is getting in a bit deep.)
Beyond that, some autoconfig is preformed via the bonjour/avahi protocol. This is where the interface box advertises what it can do (in this case, provide an internet connection) and the computer configures itself appropriately. You need avahi-daemon running for this.
You could have the firewall setting too restrictive. Have you done anything to configure the firewall?
You should be able to ping your network interface box. if not, what happens?
If you are using network manager or wicd, I wouldn't have expected this to be an issue as it does a lot of stuff 'automagically'. It is worth checking that you have got the most up-to-date version of nm, as early versions certainly had cosmetic bugs and maybe more serious ones, too.
Last edited by salasi; 08-05-2009 at 06:53 AM.