First, welcome to the world of Macs! You'll find your experience with your PB, um, different from any PC you've ever used.
OS X comes with both Internet Explorer for Mac, and Safari; I find Safari to be a more efficient browser, and it's better integrated into the OS. It looks better and renders pages better too.
If your PowerBook comes with an AirPort card, it will see your wireless network and offer to connect to it. You should think seriously about security on your network, though, and consider upgrading to an 802.11g wireless router because of the security features inherent in the newer generation of wireless equipment.
I "don't know nuthin'" about MSN or Verizon, but you will probably get more responses to this thread about them. If you are thinking about this in terms of an ISP's installation disc, you almost certainly won't need to do anything to get your PB online, since your wireless router handles the connection chores.
Good luck, and again, Welcome!