According to the plans in "Star Trek Star Fleet Technical Manual" by Franz Joseph (ISBN 0-345-34074-4), there are toilets in the following locations on a Constitution Class starship:
- On the bridge, they are located immediately to the right of the main display.
- In the crew's cabins (past sets of pocket doors).
- In the security section, in all of the cells and next to the security office.
- In the medical section, in the duty nurse's quarters, the convalescent ward, and next to both ICUs.
- In the engineering section, next to the heat exchangers and near the port sump tank.
According to "Star Trek: The Next Generation Technical Manual" by Rick Sternbach and Michael Okuda (ISBN 0-671-70427-3), the Galaxy Class starship has wastewater recycling on decks 6, 13, and 24. Solid waste is processed on decks 9, 13, and 34, where recyclable waste is sent for use in the replicators. I'm still looking for blueprints to show where the toilets are, but now we know where they lead.
According to "Star Trek: Deep Space Nine Technical Manual" by Herman Zimmerman, Rick Sterbach, and Doug Drexler (ISBN 0-671-01563-X), the Defiant Class starship has 13 head/shower rooms forming a semicircle around the computer core on deck 2. Also on deck 2 are head/shower rooms across the corridors from the warp nacelles. I couldn't spot any toilets in the maps of DS9, but they don't show the entire station.
wonko says: A tiny bit of trivia most people never notice: There's a toilet in the brig in Star Trek V, and what's more, Kirk actually sits on it. It's even labeled with a warning saying something to the effect of "Do not use toilet during red alert."