You need the £5pm Blackberry Internet Service which if you ask Vodafone about they should be able to sort you out, really simple once you've agreed to the service and it's all set up for you via a couple of SMS messages. I'm on PAYG with mine so the £5 is just deducted from my credit each month.
Once you have BIS you should find it really simple adding your email addresses etc. I added both a Gmail and an Orange email with no bother at all and I'm easily confused usually
Oh, and with the BIS you'll not only get push email, but also inclusive web access/ browsing and access to the blackberry services such as app store, mesenger etc.