What is a "Major Airline"?
Unofficial Terminology

In the United States, the unofficial term Major Airline is likely based on various official FAA and DOT terms. I cannot speak to use of the term outside the United States, but it may be similar, if used at all. This answer will address use in the context of US law and FAA regulations.

If a definition of Major Airline is to be faithful to official sources, that definition could be one such as the following from BusinessDictionary.com:


  US designation for an air carrier with annual operating revenue of more than one billion dollars, such as American, Northwest, and United Airlines. Also called major carrier.


However, as voretaq7 pointed out, the term Major Airline can be used to refer to the traditional "Legacy Carriers"—as opposed to newer start up carriers, the "Regionals", or low cost carriers. The terms are sometimes used interchangeably.



Official Terminology

The official terminology from which Major Airline is likely derived has a regulatory basis in 14 CFR 241, Section 4, "Air Carrier Groupings". This section describes the basis for grouping of Large Certificated Air Carriers, and defines the various groups. The following gives the criteria for assessing the level of operations (note that the nature of operations is assessed separately):


  (a) All large certificated air carriers1 are placed into three basic air carrier groupings based upon their level of operations and the nature of these operations. In order to determine the level of operations, total operating revenues for a twelve-month period are used. The following operating revenue ranges are used to establish air carrier groupings:  

 Carrier Group      Total Annual Operating Revenues   
 I                  0-$100,000,000   
 II                 $100,000,001-$1,000,000,000  
 III             $1,000,000,001 +  



The DOT's Bureau of Transportation Statistics provides the following similar, but simplified, definition of Major Carrier Group:


  Major Carrier Group: Air carrier groups with annual operating revenues exceeding $1,000,000,000. 




Answer

Thus, to answer your question as to what is required for a US "airline" to be designated as "Major" in an official capacity, the "airline" must:


Be a Large Certificated Air Carrier (see definition below), and
Have a reported annual revenue of more than $1,000,000,000.




Definitions

The following are definitions as given in 14 CFR 241, Section 3, "Definitions":

1Large Certificated Air Carrier:


  An air carrier2 holding a certificate issued under 49 U.S.C. 41102, as amended, that: (1) Operates aircraft designed to have a maximum passenger capacity of more than 60 seats or a maximum payload capacity of more than 18,000 pounds; or (2) conducts operations where one or both terminals of a flight stage are outside the 50 states of the United States, the District of Columbia, the Commonwealth of Puerto Rico and the U.S. Virgin Islands.


2Air Carrier:


  Any citizen of the United States who undertakes, whether directly or indirectly or by a lease or any other arrangement, to engage in air transportation3.


3 Air transportation:


  The carriage by aircraft of persons, property, or mail.