In a previous question, Mongo described flying his Cessna with a negative ground speed in a head wind. In this situation, what is the correct thing for a pilot to do, if there is nowhere to land downwind and upwind ground speed is negative? Other answers on that page show that, for very light aircraft, descending will not always get you to a low enough wind speed that you can fly forwards.
Before even taking off, a pilot is required to get a weather briefing, including winds. Wind speeds are usually predictable and well known. If a pilot was flying against strong headwinds, with no good landing alternate, he screwed up his flight planning before he even started the engine. A headwind doesn't even have to be strong enough for negative GS, just strong enough to cause concern.
Winds vary by altitude in both strength and direction. If a pilot does find himself in such a situation, changing altitude by a few thousand feet, higher or lower, can very likely change both the wind direction and speed to something that is manageable.
This question is actually applicable to a power off emergency gliding situation, where your best option may be behind you.
The way the question is worded (and one of the reasons light GA air craft are generally designed with one wing and a bit more speed than old time Jennys) is that progress upwind will drain your energy source (be it altitude or fuel) much faster than downwind (note going downwind does not necessarily mean LANDING downwind).
Nor is this question in the realm of the impossible, as I once witnessed a light GA (152 or 172) on final inching into a 35 knot headwind in Armarillo, Texas one fine day (windmills are doing great out there).
So, going upwind is out. On your way upwind, always try to pick out possible landing sites like open fields or interstate highways. If there is no where to land from where you came from, that would be a poor trip plan.
Changing altitude may be an option, though going lower may be more turbulent. Abort ASAP if weather is marginal.
If you are flying into a headwind, that means that there is an area of High pressure to your right. Frequently, as you leave move further away from the low pressure area, the winds will diminish. This isn't always the case, but it is the PICs responsibility to check weather conditions along the route and the routes to any alternate destinations.