There's a very specific existing case study of nearly this exact question.
In the 1970s, the US Department of Energy began investigating what is now known as the Waste Isolation Pilot Plant as a means of safely storing radioactive waste for the next 10,000 years.
Considerable thought was put into the topic of signage: how to indicate to future generations, for whom the very concept or science of radioactive waste may be lost, that the materials buried in this location remain harmful in a very literal sense.
There are some interesting papers from researchers at Sandia on the topic. You can read some excerpts as well.
Do we mark it at all?
I know this wasn't specifically what you asked, but it calls into question the very premise of the exercise. Recorded history goes back only about 6,000 years. The earliest known permanent human settlements go back less than 9,000. So communicating to humans 10,000 years (or, as you posed, 50,000) in the future may simply be impossible.
One alternative (in the case of the WIPP) is simply to bury the material in as inaccessible a place as possible, and assume that any civilization able to discover and uncover it will also be able to detect the danger posed.
The Sandia panel rejected this on legal and (I would say) moral grounds.
How do you ensure the message is physically durable?
This seems to be most related to the core of your question, and the answer is fairly mundane. The final proposal calls for the use "granite monuments, 25 feet high" carrying etched messages, an information center and two storage rooms with similar granite markings, and, buried throughout the complex, the same messages etched on "nine-inch-diameter discs… made of granite, aluminum oxide, and fired clay."
In addition, the same information will be placed in various archives around the world.
How do you ensure the message is intelligible?
The plan calls for the message to be translated into the six official languages of the UN (English, Spanish, Russian, French, Chinese, Arabic) as well as Navajo, the ancestral language of the region.
But come on, how do you really ensure the message is intelligible? How do you ensure that future generations don't destroy the markers? How do you ensure that people take this seriously, anyway?
This is, to my mind, the true crux of the matter. The obvious (and somewhat pulp) analogy is to curses on Egyptian tombs – an Egyptologist might properly translate the text, but he is unlikely to take seriously a warning threatening bodily harm due to vague invisible forces.
Worse yet, the presence of the tomb encourages desecration for motives both historically minded (archeological investigation) and crassly economic (as with reuse of building materials from Roman or Egyptian edifices for more modern constructions).
The WIPP panel was quite aware of such risks, and made a number of suggestions which I will simply quote verbatim:
Each component of the marking system should be made of material(s) with little intrinsic value. The destructive (or recycling) nature of people will pose a serious threat to the marking system.
We decided against simple "Keep Out" messages with scary faces. Museums and private collections abound with such guardian figures removed from burial sites. These earlier warning messages did not work because the intruder knew that the burial goods were valuable. We did decide to include faces portraying horror and sickness (see Sections 3.3 and 4.5.1). Such faces would relate to the potential intruder wishing to protect himself or herself, rather than to protect a valued resource from thievery.
While the below messages differ from the final design, I found a certain sense of Lovecraftian poetry in their directness:
This place is a message… and part of a system of messages… pay attention to it!
Sending this message was important to us. We considered ourselves to be a powerful culture.
This place is not a place of honor… no highly esteemed deed is commemorated here… nothing valued is here.
What is here is dangerous and repulsive to us. This message is a warning about danger.
The danger is in a particular location… it increases toward a center… the center of danger is here… of a particular size and shape, and below us.
The danger is still present, in your time, as it was in ours.
The danger is to the body, and it can kill.
The form of the danger is an emanation of energy.
The danger is unleashed only if you substantially disturb this place physically.
This place is best shunned and left uninhabited.
As a final aside, the suggestions made by a poll conducted by the Zeitschrift für Semiotik and Bechtel's "Human Interference Task Force" are quite interesting in their more far-ranging conceptions – suggestions include the creation of artificial satellites that can circle the earth for millennia, genetic coding of messages into cats, and the creation of an "atomic priesthood" to keep the knowledge sacrosanct.