First of all, the distances in the solar system are absolutely tiny compared to the distances between stars. To the casual observer, the celestial sphere (by which I mean everything in the sky except for the Sun and planets) will look absolutely identical to how it does on earth, or pluto for that matter.
From a specific arbitrary point on mars, the sky will behave essentially the same. Mars is very similar to earth in its rotation behaviour. It has an axial tilt of 25 degrees (compare Earth, which has a tilt of 23 degrees), and its day is only 39 minutes longer than ours, so if one were to set up a tripod and film a timelapse of the night sky at different times of year, the result would be very similar to doing the same on earth. Its north pole is pointing in almost the opposite direction to us, so when Mars is on the same side of the Sun as us, it will have the opposite season.
Mars has ~1/100th the atmosphere of earth. This means there is much less atmospheric distortion, and the stars would not appear to twinkle so much. For instance, where I live, Canopus is often just above the horizon, and appears as a twinkling blue/red star. It would not look like this on Mars. The seeing will be way better on Mars than on Earth, although still not as good as in space.
The planets will look slightly different from Mars. This wikipedia article gives a good account. The brightest objects in the sky, in order, are the Sun, Phobos, Deimos, the Earth-moon system (which can be resolved by the naked eye), followed by Venus and the rest. The Sun will appear to have a 33% smaller radius, and shadows cast by it will be correspondingly sharper.