There are several ways to get cheap airline travel in North America: choose routes where the fares are cheapest; choose times when the routes are cheapest; shopping around; and flying on budget airlines.
How to book, when to fly
Booking in advance often gets you a lower fare. The cheapest fares are likely to be unavailable in the last three or four weeks before a flight.
You can often get cheaper airline tickets by shopping online than by using a travel agent. Some airlines even allow you to pick your seat when booking, and many offer web-only discounts.
Cheaper fares can often be had for trips that depart between Monday noon and Thursday noon, or on Saturdays. However, spending at least Saturday night at your destination may also help you find a lower fare. This policy, begun by airlines trying to profit from business travelers, is becoming less common. Monday, Friday, and summer Saturday flights tend to be crowded. Check a variety of dates if your travel plans are flexible.
Some people with very flexible schedules (and a lot of patience) save money by consistently choosing crowded flights, which the airlines often overbook. When the gate agent asks for volunteers for a later flight, these travelers pick up travel vouchers for a subsequent flight in exchange for being "bumped" from the flight.
Certain periods around holidays are more expensive and crowded than normal for all forms of commercial travel and accommodation. In the U.S., this includes: the Wednesday before Thanksgiving, the four days before Christmas, the first working days after New Year's. The holidays themselves and "shadow" days (like December 26) are often very light. Also watch out for Memorial Day weekend, college Spring Break season in March and April, and seasonal destinations (beaches in the local summer, ski areas when there's snow, New England and Canada when there are fall leaves to see, college towns when there are graduations happening, Las Vegas on weekends and Valentine's Day).
High-traffic routes between major cities are often considerably cheaper than flights to smaller cities. Consider taking public transit or renting a car for the remainder of your journey. High-traffic routes also allow you more choice of departure time and flexibility in case of missed or canceled flights.
Check the flights for all the airports near your destination city. In Chicago, consider flights into Midway Airport as well as O'Hare. In San Francisco, take a look at flights to Oakland and San Jose as well. Discount carriers often fly to these alternate airports, which may actually be closer to your final destination.
Buying a round-trip ticket is usually cheaper than buying two one-way tickets, which usually involves using the same two airports for both leaving and returning. But sometimes this is not true. Use a sophisticated cost-comparison site like Orbitz to check.
Sometimes buying a round-trip ticket is cheaper than buying a one-way ticket, even if you are only going in one direction. But some airlines have instituted a "missed flight" fee to prevent people from doing this. Be sure to check before attempting this.
If you're flying from one coast to the other, consider a "red-eye" flight that leaves around 11:00PM and arrives in the morning on the other coast. These flights are often cheaper, and you spend one less night in a hotel.
Avoid booking the last flight of the day in case you miss your scheduled flight or it is delayed or canceled due to weather or technical problems (neither are uncommon). Airlines do not provide lodging for delays caused by weather or other factors outside their control.
Price comparison sites
The best way to find a cheap fare quickly is to use a price comparison site. These allow you to check multiple airlines, possibly at multiple airports on multiple days. However it often pays to compare the offer with the price on the airline's webpage. Airlines are more likely to offer an electronic ticket and not charge handling fees.
You may also be able to search for a hotel or hostel, rental car, cruise, rail pass, vacation package, or other related items at the same site. Here is a list, in order of usefulness:
Orbitz - Major North American carriers; often finds the best price among conventional comparison sites. You can often find a lower fare by adding nearby airports and day-before/day-after to your search parameters. Also allows you to specify a price, and get an e-mail later if a suitable fare becomes available.
Travelocity - Another comparison site with the added feature of being able to find the cheapest flights available regardless of dates of departure and return. Good if you want to go to a specific destination and your schedule is very flexible. Also has a Canadian site.
Priceline - Major North American carriers. Offers a conventional price comparison with full flight details. Also offers a "name your own price" feature where you can get a lower fare if you are willing to not know the airline and time of your departure (or other details, for other services) until after you commit to buying it. (For US departures only)
Before you make a bid on Priceline, go to Bidding for Travel to get advice on bidding strategies. You'll be amazed at how much cheaper you can get a hotel room than what's being quoted on the conventional travel sites.
HotWire - Major North American carriers. You don't know the time of day your flight leaves until after you commit to buying it.
Many of these sites offer a service where they will email you when the fares for specific destinations change by a specific amount or go below a specific value.
Note that some price comparison sites may not list the best fares for low-cost airlines -- or even regular airlines. U.S. Airways, a conventional carrier, for instance, occasionally has cheap fares available only on their website.
Some airlines such as Continental and American have instituted a guaranteed lowest fare feature on their websites. This means you are guaranteed to get the lowest fare for that flight on their website. This does not mean that you will not find a lower fare on another airline, but it is an improvement over the past because airlines' own websites offer frequent flyer booking bonuses for using their sites to book tickets. For example, if a multi airline search on Travelocity showed that Continental had the cheapest flight, go to Continental´s site and book your ticket there to get the bonus. Even if Continental is no longer offering it, you will be able to avoid the Travelocity booking fee of several dollars.
The price comparison sites such as Expedia and Travelocity do NOT include results from Southwest Airlines, a major player in the discount market. You have to go to Southwest´s site to check their flights and fares.
Foreign comparison sites
Many foreign comparison sites also list domestic US flights. Sometimes they find cheaper fares than American sites.
Many discount airlines do not list their fares with price comparison sites or with travel agents. Check their web sites individually for great deals. Discount airlines sometimes have special procedures or restrictions, and may be less willing to allow you to change to a different flight or to give you a refund. Be sure you understand all special terms before booking. Discount airlines are constantly expanding the list of airports they service; check their official sites for details.
Largest Low Cost Carriers
JetBlue - All flights have DirecTV and wide leather seating for every passenger. Many flights are non-stop. Hubbed in JFK, but with focus cities such as Long Beach (Los Angeles, but different, smaller, and south of LAX)
Southwest Airlines - No reserved seats. Boarding priority depends on how early you check in at the airport. Not limited to the Southwestern US. Newly expanded in Philadelphia. New partnership with ATA at midway airport (Chicago).
AirTran Airways - Merged with the infamous ValuJet and obtained a new fleet of Boeing aircraft featuring XM satellite radio. Hub in Atlanta, but operates some direct flights between regional airports and major cities.
Pan Am - Northeastern U.S. to Orlando. (No relation to the historic international airline.)
SkyValue - Gary/Chicago to Las Vegas, Arizona, and Florida. Operated by Xtra Airways.
USA3000 - Service from midwestern and northeastern U.S. cities to Florida, Mexico, and the Caribbean.
Vision Holidays - Mesa, Arizona, to North Las Vegas, plus Grand Canyon aerial tours.
Western - Bellingham, Washington, to Arizona and southern California. Operated by Xtra Airways.
Many airlines offer student and senior citizen discounts, and have low or free fares for young children.
Most airlines will give you a discounted fare if you must fly on short notice because of a family emergency, such as a death or sudden illness. Call ahead or speak to an agent; this is not possible to arrange online.
Some areas of the United States have special flight and accommodation deals(like Hawaii and Alaska). Most of the larger online travel sites have discounted Hawaii travel but the best deals can be found on travel agencies that specialize in Hawaii as a destination - like Great Hawaii Vacations  800-688-2254. Some larger agencies like Expedia  and Travelocity  also have the volume purchases to create special pricing.
These programs are being phased out, and no longer make much sense anyway because the fare structures have changed so much. Full Y fares have come down so much, and most of the time, you are no longer restricted to full Y anyway, even when purchasing an hour before. An article has been written about this in one of the major newspapers.
Military and airline personnel are usually eligible for cheap or free travel on their respective aircraft.
"Flying standby" is when you have a ticket for a certain destination, but you don't have a seat reserved on any particular flight. You are allowed to board the next flight going to your destination that has a free seat.
Standby policies vary greatly between airlines.
If you can get them, standby tickets are sometimes cheaper than regular fare if you must book your flight at the last minute.
You may be required to pay an extra fee to fly standby.
If you buy a discount ticket, or a ticket on a discount airline, you are more likely to have to pay a fee or upgrade to a higher fare to change your flight at the last minute (or at all), even if you are just trying to fly standby.
Frequent flyer club members, students, seniors, airline employees, and other special groups are more likely to be able to fly standby for cheap or at all.
Sales and limited-time offers
Many of the airlines and price comparison sites listed above show special offers on their homepages. Also see:
PickYourCity.com - Click on the navigation tabs for Deals and Last Minute Packages.
Arriving at the airport
Arrive to the airport on time (an hour or two before takeoff, as recommended by your airline) and check in right away. If the flight is overbooked, you don't want to be bumped. (You may want to be bumped if they offer a free ticket or a coupon worth money toward your next flight, but you still need to be checked in and at the gate and available to speak with the gate agent.)
Many airlines have a certain time at which they will no longer check in passengers, because it will take too long for them to get through security, perhaps up to 30 minutes before takeoff. If you are lucky, you will get booked on the next flight for free, but don't count on it. Check with your airline if you might be delayed or if you are habitually late.
Even if you check in for your flight "on time", your airline has no obligation to get you through security and onto your flight. If the airport is crowded, your flight may depart "on time" while you are in the security line. This is uncommon, but it happens. Most likely you will be offered a standby seat on the next flight, but no apology from the airline.
If there is space available, some airlines do allow you to take an earlier flight if you happen to arrive early. This might be for free, a small fee, or a large fee. But it can't hurt to ask. Have your airline's reservation number handy, as you can usually make these arrangements on the phone.