Check that the Windows SharePoint Services Support component (under 'Office Tools') has been installed by the Office setup program. This installs an ActiveX control that provides functionality such as support for uploading multiple documents within IE. If it does show as installed use the Repair option so that Office setup can ensure it is installed correctly.
You can check if the upload ActiveX control is installed correctly by going to Manage Add-Ons in IE8. Set the filter to show 'All Add-Ons'. Under Toolbars and Extensions look for the STSUpld UploadCtl Class and ensure it is enabled. It should have a major version of 12, for example 12.0.4518.1014.
As Duey mentioned, also ensure the user can run ActiveX controls within IE. In the security zone that applies to the SharePoint site, ensure Run ActiveX control and plug-ins and Script ActiveX controls marked safe for scripting are set to at least Prompt, if not Enable. A quick check is to temporarily add the SharePoint site address to the Trusted Sites zone.