Mars has a different axial tilt than Earth. It stands to reason that the constellations will remain identical from Mars, but their locations will be somewhat different. On Earth, the North Star is used as a navigational aide. What is Mars's "North Star", "South Star", and if there isn't a star for either, what would the region look like over the North/South poles?
The location of the North Pole is 21.18 RA, 52.89 North. There is no "North Star" located there, although it is about half-way between Deneb and Alderamin. (Source). In the sourthern sky, Kappa Velorum is a good South Pole Star. Here's also a few screenshots as to what the poles would look like:
I've also added a bit of video showing how these stars will appear in the following video:
Martians could imagine a line formed by Deneb and Sadr, which have apparent magnitudes of 1.21–1.29 and 2.23 respectively (lower is brighter), compared with Polaris which varies between 1.86–2.13. This would get them a little less than 3° away from true north (compared to <0.5° for Polaris on Earth).
They could also take the midpoint between Deneb and Alderamin, but it's fainter, with an apparent visual magnitude of 2.5141. If you extend the midpoint by one seventh of the total distance between Deneb and Alderamin, you'll get pretty close to the North Pole.
Yellow is the distance between Sadr (the star above Deneb in the Cygnus constellation) and Deneb extended from Deneb. Cyan is a line from Deneb to Alderamin, with a line 1/7th of the distance extending from its midpoint; accurately eyeballing a seventh and figuring out which way the line should extend is left as an exercise for the Martians.
After some stargazing, I found Alderamin very obvious and on reflection, knowing that Sadr to Deneb points to the Martian north is only useful for remembering which way to extend the seventh (though you can just remember that Cygnus points to the North).
Cygnus is pretty easy to find becuase it's in the Milky Way, so you just follow that large cloudy patch in the sky until you find it, although there's a similar looking constelation, Aquila which also looks like a stick figure but smaller and with the arms raised at a higher angle (turns out it's actually supposed to be an eagle).
The other approximate way to find it is the same way you find Polaris from the Big Dipper using its front two stars, you just have to go 2-3 times as far and you end up pretty far away, but in the general area. Orion's belt also points in that general direction, but it's far away.