"The mind is not a book, to be opened at will and examined at leisure.
Thoughts are not etched on the inside of skulls, to be perused by any invader.
The mind is a complex and many-layered thing... It is true, however, that
those who have mastered Legilimency are able, under certain conditions, to
delve into the minds of their victims and to interpret their findings
-- Severus Snape
legens - (Latin) a reader
mens - (Latin) mind
Legilimency, a branch of magic not normally taught at Hogwarts (at least, not at Ordinary Wizarding Level) is the ability to extract emotions and memories from another person's mind. Although the word literally translates as 'mind-reading', this is considered a naive interpretation of the art by its practitioners. Someone who practices Legilimency is known as a Legilimens.
Legilimency is easier when the spell-caster is physically near the target, and when the target is off-guard, relaxed, or otherwise vulnerable. Eye contact is often essential, so it is useful for a Legilimens to verbally manipulate his or her target into meeting the Legilimens' eyes, with the fringe benefit that the target's emotional state may bring relevant associated memories to the surface (OP24, OP26). All of this seems to tally quite nicely with what is known of the nature of human memory in Muggle science.
Notice that when Harry wished to avoid discussing his vision of Voldemort's confrontation with Rookwood, and how many dreams he was still having about the Department of Mysteries, he had learned enough to avoid Snape's eyes - but Snape taunted Harry just enough that Harry forgot himself and glared at Snape rather than the potion ingredients jars, so that Snape was able to obtain a more truthful assessment of Harry's progress, which he later reported to Dumbledore, as indicated in Dumbledore's interview with Harry after the battle (OP26, OP38).
Severus Snape is both a Legilimens and an Occlumens, and is apparently better at Occlumency than Voldemort is at Legilimency, which is how he has survived in his difficult role of double agent among the Death Eaters for so long (see Occlumency).
Voldemort is a highly skilled Legilimens, in the estimation of Severus Snape (OP24), to the point where Voldemort can nearly always tell when someone is lying to him. Unlike Snape, Voldemort is never shown speaking the incantation to use Legilimency, if his first appearance in GF1 and last scene in OP36 are any indication. He is able to possess the bodies of snakes while retaining his own body, possibly through Legilimency (OP21). Through his connection with Harry, he was also able to use his ability to feed images and eventually false visions into Harry's dreams, when Harry's mind was most relaxed and vulnerable (OP24, OP38).
Dumbledore is also a Legilimens, describing himself as sufficiently skilled to know when he is being lied to. He is also sufficiently skilled in Occlumency to be able to teach it if he so wishes (OP38).
Since we've been told that the use of Veritaserum is controlled by very strict Ministry guidelines (GF27), the same should be true of Legilimency. (This would not need to be true of Occlumency, since that is purely a defensive measure and only affects the person using it.)
Teaching Legilimency may be legally restricted. For instance, a student may be required to be of age, and/or to pass character tests like those required for Auror training. Note that nobody suggests Harry should be taught Legilimency at his age, and he isn't learning it as part of Occlumency (as indicated by his thoughts during his History of Magic O.W.L.).
All that can be true without any contradictions with Voldemort having learned it illegally. Or even legally; since young Riddle was very good at maintaining a respectable public image, he might have been able to openly study the art if so inclined.
Using Legilimency may or may not legally restricted.
Consider the effectiveness of Rita Skeeter's unregistered Animagus status as a tool in gathering information, then think what she could have done as a Legilimens. Is it likely that the Ministry (a government entity full of career bureaucrats and politicians) would fail to regulate the use of Legilimency?
Severus Snape and Albus Dumbledore do not appear to have ethical qualms about using Legilimency in teaching Harry, nor do they appear to fear exposure for doing so. They merely arrange a cover story for Harry's lessons (taking remedial Potions) and request his discretion about the extra tutoring.
There may be restrictions on the circumstances under which a Legilimens may reveal something learned via the technique, analogous to the confidentiality restrictions that apply to Muggle lawyers, physicians, psychiatrists, and clergy.
"Snape gave Harry a swift, piercing look. Harry looked at the floor." (PS10)
This is immediately after the mountain troll incident, and McGonagall has just asked why the kids weren't in their dormitory, just before Hermione stepped in and lied to protect the boys. Since Harry didn't maintain eye contact, Snape would have had some difficulty in exploiting Legilimency to determine if Hermione were telling a straight story or not.
"Could Snape possibly know they'd found out about the Philosopher's Stone? Harry didn't see how he could - yet he sometimes had the horrible feeling that Snape could read minds." (PS13)
If Harry only knew.
"Now...why don't you give me that Stone in your pocket?" (PS17)
Voldemort to Harry. This is almost certainly an instance of Legilimency, since Voldemort now knows exactly where the Stone is, and Harry hasn't been able to move enough since he got it to give himself away with a gesture.
"This wasn't the first time Snape had given Harry the impression of being able to read minds." (CS5)
Snape had just asked 'what have you done with the car?', having just caught Harry and Ron after their late arrival.
"[Dumbledore's] twinkling light-blue gaze made Harry feel as though he were being X-rayed." (CS9)
Snape had just suggested that Harry wasn't being entirely truthful about why the trio hadn't gone to the Halloween feast after the Deathday Party (quite correct, although it didn't require Legilimency to figure that out).
"Snape's eyes were boring into Harry's. It was exactly like trying to stare down a hippogriff. Harry tried not to blink... 'Malfoy is not having hallucinations... if your head was in Hogsmeade, so was the rest of you.'" (PA14)
Snape is interrogating Harry after the mud-slinging incident in Hogsmeade, since Malfoy just reported it to him. Harry is trying to look innocent, and so he's meeting Snape's eyes - not realizing who he's messing with.
"Harry bit his lip. He didn't know what had happened and didn't want to admit it - but Snape seemed to have guessed the truth." (PA14)
Angered by Snape's slurs on James Potter, Harry had just lashed out, revealing that Dumbledore had told him James once saved Snape's life. Snape is now establishing just how much Harry knows about the incident.
"Or - instructions to get into Hogsmeade without passing the dementors?"
Harry blinked. Snape's eyes gleamed. (PA14)
Harry is therefore meeting Snape's eyes, just after having turned out his pockets for Snape, revealing the Marauder's Map in its blank parchment state. Harry's reaction up to this point has established only that it's something important to him. From this point in the conversation, however, Snape goes to work trying to force the Map to reveal its secret.
"'But you seem so much stronger, My Lord -' 'Liar.'" (GF1)
"'I - I thought she might be useful, My Lord -' 'Liar.'" (GF1)
"'Don't lie to me,' Snape hissed, his fathomless black eyes boring into Harry's. 'Boomslang skin. Gillyweed. Both come from my stores, and I know who stole them.'" (GF27)
Harry had been ignoring Snape's needling up to that point, until Snape finally goaded him into meeting his eyes. Unfortunately for Snape, he and Harry are having different conversations at this point without realizing it. If he'd continued to press Harry on these points, the whole business of the undercover Death Eater at Hogwarts could have been blown open right then - but the conversation doesn't play out that way.
Harry believes the mention of boomslang skin to be a reference to the CS11 incident in his second year, and doesn't know anything about any more recent thefts of it from Snape's private stores, so Snape could not have learned anything about the more recent incident by using Legilimency on Harry here.
As for the gillyweed, the logical thing for Snape to have suspected up to this point was that Harry had taken it himself, not that anyone had taken it for him. Even if he learned through Legilimency that Dobby took it for Harry, Harry at this point is not thinking of how Dobby learned about the gillyweed, so Snape couldn't have learned it from Harry just by Harry's reaction to this question.