If I want to attach the brand label of my company to computer hardware
OEM products I sell - e.g. like Compaq labeled OEM Logitech mice as
Compaq mice, Maxtor hard drives as Compaq hard drives, and Matrox
video cards as the Compaq's QVision 2000+ video card - do I need to
have a contract with the OEM manufacturer, do I need to fullfill the
requirements of some licence, or can I just start placing stickers on
the OEM hardware stating "such-and-such small computer shop"?

Under trademark law you are free to resell another company's products,
using their trademarks and branding, without a license.  So, you could
buy 1,000 Logitech mice and advertise them as Logitech mice without a
trademark license.  What you are proposing, however, is co-branding,
and that is different.  Because you are placing your brand onto the
other company?s product along with their brand, there is a possibility
that it will be looked upon as a form of source confusion by
consumers. i.e., they will not know who is making the product for
sure.  Moreover, the manufacturer may object to your co-branding
because it creates the appearance that they are sponsoring or
endorsing your product line.  So, you should approach the
manufacturer(s) about a co-branding agreement.

Am I wrong in assuming that the manufacturer's brand will also appear
on the products, or is this a private label deal where only your brand
will appear?

Yes.  In order to become an OEM dealer or change an OEM device, you
need to arrange to become a distributer for the particular company
that you are buying OEM devices from.

Companies require an OEM contract signed in order to sell as a
legimate distributer and to alter any devices.  Not only does this
contract give you a price break, but it also frees the manufacturer of
any burdens or liability on the product that you are reselling.

You can contact most companies and ask how to become a business
partner/distributer.  This way, you will also get better deals on
their equipment, and change the item however you need.

An example of this is your computer.  Did your computer come with
Windows already installed?

Right Click on "my computer" and go to properties.  Near the bottom,
it will tell you who gives free support for your windows software. 
Also, under "Registered to:" The second group of digits will say OEM,
telling you that the Windows Software on your computer actually
belongs to the Manufacturer of the computer.

Microsoft sells "Windows XP" over the shelves.  Dell (or your computer
manufacturer) can buy microsoft Windows for cheap and change the
drivers, or any startup options or the registry.  They also agree to
support Windows XP, taking the burden off of Microsoft for finding the
way that the OEM has changed the software.

Thanks a lot for your advice, ipfan and lifejustice, it was just the
information I was seeking!