Sounds like you have a browser hijack. They can be very hard to clean.
If it's a new laptop then you can't have much important stuff on it yet. I'd be inclined to restore it to factory settings, if they gave you a disk.
Get your virus checker on before connecting. Then as soon as you get connected, get the Microsoft Anti Spyware thing and all the M$ updates, as well as updating the virus checker, before you start browsing anywhere else.