The A* search algorithm (pronounced "A-star") is a procedure for finding the optimal path through a weighted graph (that is, a network of edges between nodes where the edges have values associated with them). The applications are most obvious in pathfinding through a 2-dimensional or 3- dimensional space, which is why many robotic systems use A* to find their way through their environment.
It's based on Djikstra's Algorithm, which was developed by Edsger W. Dijkstra in 1956. The improvement developed in A* was the addition of a heuristic function to estimate the cost of traversing unvisited nodes, which reduced the number of nodes which needed to be visited. Engineers Peter Hart, Nils Nilsson and Bertram Raphael published it in 1968 as part of the Shakey project, which produced a robot with greater autonomous capabilities than any before it.
A* was formerly named A2, and there was an A1 before it. A2 was renamed A* because it can be proven to be optimal (under certain conditions) and no future version of the algorithm can improve upon it; the * represents all future versions.