As evidence of caverns detected on Mars, consider the following recent image taken from HiRISE instrument on the Martian Reconnaissance Orbiter :

Image source: NASA
Scientists believe that
The hole appears to be an opening to an underground cavern, partly illuminated on the image right. Analysis of this and follow-up images revealed the opening to be about 35 meters across, while the interior shadow angle indicates that the underlying cavern is roughly 20 meters deep.
Which accompany larger openings, reported in the National Geographic article Mars Has Cave Networks, New Photos Suggest (Norris, 2007) of several larger pits detected by Odyssey, and they offer a possible origin:
The surface of Mars is strewn with craters from meteor impacts and depressions formed by the collapse of underground chambers formed by flowing lava, the experts said.
There are many examples of lave tubes (and indeed, in other places in the Solar System), caverns etc reported in the article Mars Cave-Exploration Mission Entices Scientists (Wall, 2012), who also state, in regards to detection and exploration of these caverns that robotic means are being explored.
However, according to this NASA article, a method to find and characterise caves on Mars (or indeed Titan, and maybe other places, including the Moon) is to detect them via thermal differences caves cause in comparison to the surrounding surface. This method is used on Earth, and
Techniques developed
through this research will ultimately be applied to
locating subterranean cavities on the Martian surface.
We anticipate one of the best techniques for systematically
finding caves on Mars will be via remotely
sensed thermal imagery.