Is this normal behavior ? Is there a way to avoid this ?
It is normal behaviour for non-wired connections. Network Manager handles the connection of wireless (and wired to some extent) connections and that won't jump into action until a privileged logs in.
You can circumvent it slightly by enabling auto-login (through System -> Administration -> Login Screen Settings) but this would reduce security. You could hop around that problem by having the desktop lock itself by adding xdg-screensaver lock as a start-up application (System -> Preferences -> Start up applications).
As João suggests, you'll probably need to make the connection "Available to all users" so that it doesn't ask for a keyring password (which obviously wouldn't get entered if nobody was there).
That's probably only practical if it's a single-user machine and it might not be as secure as not logging in at all.
Another method would be to take away the connection from Network Manager and have the underlying networking layer do the connection. You could try something like this in your /etc/network/interfaces file:
auto wifi0
iface wifi0 inet dhcp
wireless-essid YOUR-AP-ESSID
wireless-ap 00:11:22:33:44:55
wireless-key YOUR-AP-KEY
Obviously replace wifi0 with the wireless interface, YOUR-AP-ESSID with the wireless access-point's ESSID, 00:11:22:33:44:55 with the MAC address of the AP and YOUR-AP-KEY with the proper key.
This has the side effect that anybody on the system can just cat /etc/network/interfaces and find your AP key. That might be bad... It depends on how secret it needs to remain. But only logged in people could see it.
This might not work and it might even make Network Manager explode. I can't say.
In the same vein as above, here is a blog post about using wpa_supplicant and /etc/network/interfaces: http://blog.nelhage.com/2008/08/using-wpa_supplicant-on-debianubuntu/
It's quite a old post but it might be slightly more secure than straight-up embedding your connection information into /etc/network/interfaces.
If we're just talking about a wired connection...
I notice that on newer installs of Ubuntu, the auto-connect state has been removed from /etc/network/interfaces for desktops. I guess Network Manager is doing that now. To add it back in, edit the interfaces file to add this:
auto eth0
iface eth0 inet dhcp
And for a static (non-DHCP) connection here's an example from one of my servers:
auto eth0
iface eth0 inet static
address 95.172.14.178
netmask 255.255.255.248
network 95.172.14.176
broadcast 95.172.14.183
gateway 95.172.14.177
# dns-* options are implemented by the resolvconf package, if installed
dns-nameservers 78.40.32.140
post-up ethtool -K eth0 tx off
Some of those can be ignored or left to auto.
