What would be the challenges for a pilot taking off into a headwind of just under the clean stall speed?

Robert has answered the question quite well, but I will elaborate:

Taking off into a strong headwind is not difficult as such, but as Robert (and John as well, in less subtle way :) pointed out, taxiing in strong wind, however steady it might be, is a real pain it the seat of the pants. Since the question is about taking off, lets assume the plane would (magically) get to the end of the runway safely. The takeoff itself would then be something along the lines of what can be seen for example in this video:

Youtube: STOL Competition - World Record Shortest Landing 9 Feet 5 Inches (Yes the title says "landing", but there are plenty of takeoffs to be seen)

Nothing special really, except you are airborne in a blink of an eye. What might be troublesome to an inexperienced pilot, is that the visual cues are weird, so airspeed would have to be monitored with great care as referencing the surroundings would be useless. Also: great wind speed at ground level guarantees there will be turbulence, so maintaining appropriate airspeed is critical, and lifting off the plane should be "decisive" to avoid being pushed back on the ground by shifts in wind. The question states a wind speed just under clean configuration stall speed, so you would not use flaps, since as soon as you would lower them, you would lift off.

As for the part of "Is this something that happens often?": No. Outside the realm of STOL contests, during normal operations: this does not happen. Regulations and POH limitations set aside, you just could not get on the runway in one piece.

P.S. It is worth noting that majority of STOL contest planes are taildraggers, so this gear configuration certainly is not a disadvantage when taking off or langing at windspeeds closing stall speed.

"Fairly steady" wind is the only wording that would make it even remotely considerable, with risks of being ground looped or blown over while taxiing.

One scenario may be a light GA plane taking off from a moving aircraft carrier.

Tricycle gear would be a tremendous advantage, as this would help keep the wing at a very low angle of attack to the wind. This allows the plane to remain on the ground during its takeoff run long enough to establish a safety margin in airspeed before the plane "rotates" to an angle of attack sufficient to generate enough lift to fly.

One must be aware, although this is doable, gusts make it extremely dangerous. Far better to wait for better weather.

Even with no wind, the safe rotation airspeed will be higher than the clean stall speed.

The main challenge would be the long walk back to the airport, assuming you could still walk, after your airplane was blown like a tumbleweed into the next county. In other words, it's simply not something you would even try. Only very experienced or foolish pilots will even go out in winds approaching 50% of stall.