I typically include jQuery (and sometimes SPServices) in my actual branding solution. I consider it one of those core components that I typically make available throughout the entire environment by way of the master page.
I'll generally use my branding feature to deploy minified jQuery to the 14 hive, and load it in the head of my master page. If I have jQuery script that will be executed throughout the entire environment or common between multiple master pages, I'll typically break that script out into my own .js file and load that in the master page (after jQuery). This makes the maintenance of such scripts a little cleaner since they're no longer embedded in the master page (and eliminates duplicate script in some scenarios).
Many people will deploy jQuery to the Style Library, and while there's technically nothing wrong with that, I tend to prefer deployment to the 14 hive. This makes version management a little easier, and also ensures that your users only cache jQuery once. If you're storing the source in every site collection's Style Library, your users may be caching the same file multiple times since it has more than one path.
As for your specific question about users not seeing it, I concur with Eric's suggestions. Make sure that your jQuery library is checked in, and available to everyone (if it's not in the 14 hive), and make sure that your master pages are approved; it sounds to me like a simple case of something not being accessible by your users.
You can also verify some of this using an analysis tool like those in Google Chrome, or even Fiddler (though Fiddler may be a bit overkill), to validate that the jQuery source is being called and not throwing a 404, 403, or some other error.