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.