I would guess something else you've installed is zapping the Google toolbar. Several downloadable goodies include other stuff you didn't ask for: you have to untick them or they will be installed as well as the item you want.
That said, I don't use the Google Toolbar: the Firefox user-configurable toolbar is extremely flexible, and includes all the Google stuff I use plus a lot more besides.