They were probably made in a slightly dried mud, then sand or other light particles were blown over. Over time this was compacted and the mud became harder than the sand. They are probably still not so hard that you wouldn't have to be careful to reveal them.

There have been some trackways found from dinosaurs, so they can last even longer.