So to me, skim means to start at the beginning and go through pages looking for words or phrases that are noteworthy in order to glean the general meaning of the text. Peruse, to me, connotes something more exploratory, more open-ended. You can start anywhere and if you see something interesting you may read it closely. You're not looking to get the general thesis but just sort of seeing what is there. Skimming is the equivalent of an artist looking at a scene and trying to sketch the general outlines and shapes she sees. Perusing is the equivalent of an artist looking at a scene, maybe finding something she likes and drawing that, and then maybe move on to another part of the scene and sketch that instead; she moves around in no particular order- just noticing things about the scene.

But maybe that connotation isn't universal.