Relative velocity is the velocity of an object B, in the rest frame of another object A. This is denoted as $v_{AB}$, where A is the velocity in the rest frame of B.

Galileo observed the concept of relative velocity by using an example of a fly and a boat. He observed that while you are aboard the boat, if you see a fly, you can measure its velocity, $u$. You can then go back on land and measure the velocity of the boat, $v$. Is the velocity of the fly, $u$, the actual velocity of the fly? No, because what you measured was the velocity of the fly relative to the velocity of the boat. To obtain the velocity of the fly relative to the shore, $s$, you can use the vector sum as shown: $s=u+v$

Examples of Relative Velocity

This concept is best explained using examples. Pretend you are sitting in a passenger train that is moving east. If you were to look out the window and see a man walking in the same direction, it would appear the the man is moving much slower than he actually is. Now imagine you are standing outside and observe the same man walking next to the train. It will appear the the man is walking much faster than it seemed when you were inside the train. 

Now, imagine you are on a boat, and you see a man walking from one end of the deck to the other. The velocity that you observe the man walking in will be the same velocity that he would be walking in if you both were on land. Now imagine that you are on land and see the man on the moving boat, walking from one end of the deck to another. It will now appear that the man is walking much faster than it appeared when you were on the boat with him. 

Why is this? The concept of relative velocity has to do with your frame of reference. When you were on the train, your frame of reference was moving in the same direction that the man was walking, so it appeared that he was walking slower. But once you were off the train, you were in a stationary frame of reference, so you were able to observe him moving at his actual speed. When you were on the boat, you were in a moving frame of reference, but so was the object you were observing, so you were able to observe the man walking at his actual velocity. Once you were back on land, you were in a stationary frame of reference, but the man was not, so the velocity you saw was his relative velocity.