A point that the other answers so far perhaps don't make clear enough is the decentralised nature of the Internet back then.
We've got used to the idea that every type of content is accessible at some central location (whether that's a single server, a whole data centre, or even a group of data centres all accessible at single address or web page). But that's not how the Internet started, nor even how it was back in the '90s when Usenet was still hugely popular.
In fact, the Internet developed from military systems which were specifically designed not to rely on big central servers with single points of failure. And some of that mind-set persisted.
Usenet messages didn't live on a single server anywhere, because there weren't any organisations you could trust to run such a server reliably over the long term — certainly not without charging its users for the privilege. And even if there were, you couldn't rely on being able to access them reliably at any time. And even if you could, that access might be slow, and/or cost.
So Usenet developed to be decentralised: messages were send on from machine to machine, in batches, ending up on your nearest server from which you could collect them in one go — and then read them off-line at your leisure.
That's a very efficient approach: the transfers are done across direct links, perhaps when they're less busy (or cheaper); messages only need to be transferred once regardless of how many users will end up reading them; and reading can be done off-line without incurring any further costs. (Yes, Internet access could be expensive back then. I remember using dial-up access — which incurred per-minute charges even though it was a local number in the UK — and having to watch the time carefully and transfer as much as possible in one go so that I could then use it after disconnecting.)
With the advent of unmetered, always-on Internet connections (that didn't tie up your only telephone line!), rapid transfers, highly-reliable data centres, and business models that provide all sorts of services without any direct charges (discounting the indirect costs associated with advertising, usage of your data, malware, censorship…), things have undergone an enormous shift towards centralised services. And there are of course advantages to that (as well as some disadvantages).
You can see a similar shift with another non-web application on the Internet: email. Back in the day, email would be sent via a series of email servers (some belonging to big organisations, others less so), but it would end up on your machine, whether that was an account on a system belonging to your employer or university, or your own microcomputer/PC. That's where the mail would live; the only place it would be accessible. Some people still use mail clients which work that way, but most now use web mail instead, with the mail living on big servers belonging to your ISP, employer, educational institution, or some unrelated organisation — accessible from anywhere with a net-connected web browser, but no longer under your control.
Even the early web was much less centralised; most web sites were small, and finding them was hard enough that they organised themselves into web-rings and link pages.
So, to answer the question: Usenet messages physically lived on all the news servers carrying the relevant newsgroup, along with all the clients to which people had downloaded them. Those servers were mostly at universities, Bell Labs sites, Unix-related companies, and ISPs.
