What is a prime minister?
A prime minister is a legislator who serves as the head of a state's government. You don't need a
monarch, a separate
head of state, or an address in
Asia to have a prime minister. What you
do need is a
parliament... or something similar, like a
National Assembly,
Diet,
Rathasapha,
Knesset,
Sansad,
Oireachtas, or
Folketing.
The concept of the prime minister originated in Europe, and is their preferred system of republican rule over the American concept of a president. The difference between a prime minister and a president, in less than ten words, is that presidents are elected by the people*; prime ministers aren't. If you want to be a president, you have to campaign to the people. If you want to be a prime minister, on the other hand, you have to campaign to your fellow politicians.
Here's how it works in most countries. You have an election for your legislature, and fill the chambers with a few hundred right honourable members. When you manage to get all of these lawmakers in one room, you ask them to select a prime minister from among their ranks. If one political party has the majority there, they simply elect their party's leader to the top spot. If nobody has a majority, a few parties get together and agree on a common candidate to vote for (a coalition). Essentially, the citizens delegate their votes to their representatives in the capital.
Prime ministers can be lumped into two broad categories: dudes with all the power, and dudes with only some of the power. The United Kingdom is the textbook example of the former, while France is the textbook example of the latter.
"Dudes with all the power" are found in countries like Britain, Canada, and Japan. Once they are elected, they are the top dogs in their respective countries, and get most (if not all) of the administrative power that would be afforded the president of the United States of America.
"Dudes with some of the power" are found in countries like France, Germany, Russia, Italy, Israel**, and Ireland. In these cases, there is a separate president (or chancellor or whatever) who is elected by the people and can do a variety of things over the prime minister's head. Sometimes (as in Israel's case), the president is more or less a figurehead in comparison to the prime minister. In other cases (such as Ireland's), the prime minister gets trampled by presidential power more often.
Prime ministers are often tied to constitutional monarchy, but the two are not mutually inclusive. All the constitutional monarchies on Earth today are prime ministerial in structure, but not all prime ministers are serving in the name of a Majesty or Imperial Highness. In most cases, a prime minister without a monarch will be a "dude with some of the power": the only prevalent exception is when the Communist Party is in charge. There are, however, a handful of republican assemblies in the Somewhat-Free World that have supreme prime ministers: the Grand National Assembly in Turkey, the Jatiya Sangsad in Bangladesh, and the Dewan Perwakilan Rakyat in Indonesia.
* OK, cut it with the Bush-Gore jokes already...
** Between 1996 and 1999, Israel's prime minister was the only prime minister in the world directly elected by the people. The electoral system didn't work in a parliamentary context, however, so the Knesset reverted to its old ways.