The Western is a genre dating back to the time of the actual settling of the American West, when Americans back East turned their attention from the adventure stories of the sea, to the adventures of man on dry land. As more and more moved Westward, many of them immigrants, more and more curiosity arose, until finally the West became accessible to everyone, when the trains stretched from New York to Los Angelas, and the frontier was finally closed. Cowboys and the Western tradition would not be so easily forgotten, though, and novelties like Wild West shows sprang up across the country. With the dawn of film came another new boon for the genre, and the recent advent of video game consuls has also given the Western a surprising, if deserved, boost. There are three essential elements in making a story a Western, and they are vital. To be considered a member of the genre, a piece of storytelling must take place in any state from Missouri and Arkansas and farther west or the corresponding region of Canada or Mexico, must include a romance as either the main plot or a subplot, and and take place after 1835.
The first and perhaps most obvious of the things that make a Western a Western, is, of course, the West. The prairie states, Kansas, Oklahoma, Nebraska, Illinois, etc. are the least widely used of the various groups, although stories like My Antonia use the majestic, rolling seas of grass to paint a picture of frontier life like no other, and the diverse Indian and immigrant populations make for a great cast of characters. The "classic" Western states include Texas, Colorado, New Mexico, Arizona, Wyoming, Nevada and Montana, all of which have strong histories of violence and ranching, majestic landscapes and diverse people. Finally, the outlying states, all important to the genre, are California, Idaho, Arkansas, Missouri, Oregon, Washington and the Dakotas, each one of which has a very special flavor and creates unique stories simply through a unique setting. Also, Canada, a wild frontier even today, and Mexico, a mythical outlaws El Dorado, are important settings to, often employed for contrast or as a secondary locations; perhaps a place to lay low or experience some worldly event that expands the characters knowledge and experience, or as the source of more mysterious "foreign" characters.
Romance is vital to the Western. Weather its the blonde beauty from back east, unaccustomed to the rough life of the frontier, or the dashing, dark Mexican senorita, romance is found, without exception, in the genre. The first reason this is true is because romance is one of the key driving forces behind the desperate actions of human beings, and often produces a rich emotional backdrop, vital to characters who are often diamonds in the raw, "bad boys" or strongly controlled by their emotions. Secondly, it is because women provide a contrast of morality to the rough men of the frontier, and often present a dilemma to the story line and the characters. High Noon, the mid-20th century American film, is an excellent example, providing the main character, a town marshal, with a complex relationship with two women, and the contrast of viewpoints on the movie's dangerous outlaws both with the Marshal and with one another.
Finally, it is essential that a Western take place after 1835. The fall of the Alamo, in 1837, is considered the beginning of the wildness of the West, and anything before the events leading up to Mexico's war with Texas is often considered of pioneers or American colonists. Up until this point, settlement was heavily controlled by Washington and by already existing states, livestock farming was not considered a major way of life in the United States, and many of the territories where populated by few but Indians and the military until the Civil War. So, to have a true Western, you'll need a diverse cast of characters, only available in the period after 1835. There is only one exception to this, and that is Mexican settlers in the early 1800's, in California and the desert southwest could also fall under the category of Western, as they would fall perfectly into the first two guidelines.
Westerns are valuable parts of the American literary tradition, and are easy to pick out. They take place in the wild-lands of North America, out across the Mississippi. All of them involve romance as a plot device or as the plot itself. Finally, they must, with one rare exception, take place after the year of 1835, and can take place all the way up until the present, the final installment in the Call of Juarez o series or Cormic McCarthy's No Country for Old Men being excellent examples. These qualifications might be the basics, but the Western genre actually is more of a mega-genre, where these guidelines give birth to stories in every other categor.