The term magic realism was first used by the German art critic Frank Roh, initially to describe a group of painters in the 1920s who were in the process of recreating traditional depictions of reality. Today, magical realism is used especially when referring to Latin American literature; it was first applied to such literature by the critic Uslar Pietri, but only came in vogue after Nobel prize winner Miguel Angel Asturias defined his novels as fitting into the style.
It is difficult to distinguish magic realism from conventional fictional realism. After all, the very plots, characters, and narrator of conventional fiction are not truly realistic. However, stories of magic realism tend to treat reality as completely fluid and have characters who accept this as normal. An encyclopedia reshapes the world to fit its descriptions or a stream of blood travels to tell a woman of the death of her husband, and the characters simply accept these unprecedented happenings as more events in their lives.
Note that magic realism often arises in societies with repressive, authoritarian, or totalitarian governments, and may represent an accommodation to a severely dangerous form of political reality. On the other hand, magic realism has spread beyond these confines.
Unlike hard science fiction, which is limited by the laws of physics (or at least pretends to be) or some types of fantasy which have consistent rules within themselves (you have to throw a specific ring into a particular volcano), magic realism is whimsical, or at least very particular to the society it depicts.
For instance, many of García Márquez's novels appear on the surface to be journalistic accounts of real-world events, but on closer inspection the stories have a sheen of unreality and mystery that cannot be explained by any journalistic techniques. Magical realism is not a movement or school, it is a prose style. It has no formal connection with surrealism.