First, make sure you've downloaded the latest version of Google Earth. You can get it at earth.google.com. Mars is not included with any version prior to Google Earth 5.
Once you've done this, open Google Earth. You'll notice a set of buttons on the upper right corner. One button looks a bit like Saturn. We can't visit Saturn yet, but it's the planet easiest to turn into a symbol. Press the Saturn-like button and select Mars from the drop-down list.
This is the same button you'd use to switch to Sky view or to switch back to Earth.
Once you're in Mars mode, you'll see that the user interface is nearly identical to Earth. You can turn information layers on and off, search for specific landmarks, and leave Placemarks.