How do VFR pilots know whether or not they are inside controlled airspace if they don't have GPS onboard?
VFR aviation maps called "sectionals" (and now GPS map displays) depict the types of airspace through borders with different colors and dashed lines. You can buy or download the maps for free from this FAA site.
It is always the responsibility of a pilot to know where they are and follow all applicable laws. In the US, a pilot that breaks a rule because they didn't check NOTAM's can expect certificate action. NOTAM's will inform the pilot of TFR's, "hot" military zones, and other important regional and local (i.e. airport) regulatory information.
I got my PPL in 1975 and still carry maps with me. I plot an "X" along my route every 10min of flight time (20-30mi). As I reach each checkpoint, I follow a very old axiom, "Never.. Ever.. EVER!.. proceed to the next checkpoint until you identify where you are and what corrections are needed for the next checkpoint". In this manner, you can never be further than 1 or 2min and 1-2 mi from where you should be.
Even when sightseeing with no particular route, I routinely mark a map about every 10min with my location. In my 2500hrs of flying, the most I have ever been off in my navigation was 10mi (even when flying 1500mi x-country). So, knowing where you are is not difficult if you practice the skill.
The front of the map has a legend to remind pilots what the coloring stands for.
Sectional map (US Gov public domain)
Front map legend (US Gov public domain)
Use of a sectional chart and pilotage.
You will have to be aware of where you are using ground references while cross referencing where the boundaries of controlled airspace lies in relation to those references.
For example if you’re flying around to the west of John Tune (KJWN) airport in Nashville, TN and will notice the river bends near the airport. Anything to the east of them lies in the Nashville Class C shelf between 2400 and 4600 ft MSL. A similar process can be used to assess your position relative to the surface area of the Class C airspace.
You can also pinpoint your location if your aircraft has two NAV radios and OBS heads using the intersection of two VOR radials or one NAV radio and a DME by locating you polar position relative to the VOR.
Generally: By Using a (Physical) Map
Aviation charts have landmarks and airspaces on them, which you can use to estimate where you're at. Other answers give great examples of this already, I don't have to repeat it.
But I thought I could add some real life experience here:
1) Memorizing the Area
Glider pilots, especially trainees, often fly without maps and GPS. As they tend to stay close to their departure airfield, they can be sure to not get into controlled airspace. Trainees generally memorize beforehand where such airspace begins, for example at my old aviation club we knew we had to contact a nearby airfield when going above a certain altitude, and going past the nearby city to the north would also lead into that airspace.
This of course restricts these pilots to only flying within this well-known area, as anything beyond could or could not be controlled.
2) Planning a Route Ahead of Time
I have flown cross country without any GPS for training purposes when I was a student pilot. My trainer and I plotted our route using the map before even going to the airport. We planned to fly along highways and other highly visible landmarks in order to keep our orientation and avoid controlled airspace. This way we barely ever needed the map while flying and still knew where to go.