I don't think that this is an update issue. I think that the package is simply not installed.
MiKTeX has the option to install missing packages on-the-fly. You can check if this option is enabled by looking by opening the "Settings" application of your MiKTeX installation.
This application can be found by going to:"Start Menu --> MiKTeX 2.x --> Maintenance --> Settings". At the bottom of the first tab, the "General" tab, there should be the option to enable the "on-the-fly installation process". This should solve any issues with missing packages when you compile your documents.
In the same "Maintenance" folder you will also find the applications to update ("Update") and manually manage the packages to be isntalled/removed/updated ("Package Manager"). More information on those two can be found on the link provided by cmhughes.
I hope this has cleared some of the maintenance work needed to install/update/remove packages.