
Ahh.. A question that lies on our tongues quite often. Too often, some might say.
American Cheese is not cheese, at least in the traditional 'Separate curds from whey and then pack the curds' cheese-making process that, y'know, actually makes real cheese. That's not to say that there isn't real cheese in American cheese. There is. But the cheese is also processed with emulsifiers, preservatives (sometimes something as simple as salt, other times with various chemical compounds) and often food coloring. These additives are what make defining American Cheese so difficult.
You see, each type of cheese out there is based off of a well defined enzyme that gives it a particular taste. That's one of the items that makes the difference between a Gruyere and an Edam (another items is the process in which enzymes and bacteria are introduced to the cheese, but that's a different post). Whether you take bite of an high quality Edam or one of mediocre quality, you should still be able to say "This is an Edam Cheese".
American Cheese is not really based off of taste as much as texture. American Cheese holds together very well and melts into a gooey blancmange. It's why we tend to use the cheese on burgers and other heated sandwiches: because it adds a gooey texture to the sandwich that we find palatable. The taste? Meh. We Americans don't care how the cheese tastes so much as long as it gives us a good mouth feel. That's why Kraft has a multi-million dollar cheese product line, instead of being a laughing stock of cheese-eaters everywhere.
Some American Cheese "makers" add so many items to their American Cheeses that they can no longer call it "Cheese". In its place we get items like Cheeze Whiz and Velveeta. These products are sold as "cheese food", "cheese spread", or "cheese product", depending primarily on the amount of cheese, moisture, and milk fat present in the final product.
So, rather than ask "What is American Cheese?", one would get a quicker answer from the missive "What isn't American Cheese?" to which one would reply "It isn't cheese". It is, however, a non-standardized cheese-variant popular more for its texture than taste.
Oh, and it's orange, only because we Americans think cheese should be orange. But that's another story for later.
If it just says "American Cheese", with NO other modifiers, I believe it really is made of almost entirely cheese ("cheddar cheese, washed curd cheese, colby cheese, granular cheese, or any mixture of two or more of these may be designated as ``American cheese''."). If it says "Pasteurized Process" Cheese, with NO other modifiers, it is still almost entirely made of cheeses (2 or more varieties blended together) but can have something like 5% added milkfat/cream/whatever, 3% emulsifiers, and a small amount of other additives (acidifiers, food coloring, etc.)
When you start adding other modifiers to the name is where you start getting into the stage of being made "with" cheese instead of being made "of" cheese. "Pasteurized Process Cheese Food" is only required to be 51% cheese. "Pasteurized Process Cheese Product" is the same thing, but without the 51% requirement: yes, "cheese product" can be almost entirely "not cheese".
The "cheddar is orange" thing is because nice, healthy grass-fed dairy cattle will seasonally end up producing yellowish-orange tinted cheese due to the carotenoid pigments they get from the grass. Same thing goes for yellow butter. People being obsessed with their fear of variation, retailers took to dying the products so they'd always be a consistent color. In the US, at least, people often think of "cheddar" as the default real cheese, which they also always assume will be orange. Therefore, fake-cheese makers will dye their product orange to make people think what they're buying actually IS cheese, even if it's really just "cheese product".
The Code of Federal Regulations defines it all: you can find the cheese stuff in 21CFR133, which I would provide a link to if the blog allowed anchor tags (grrrr....)...
Instead, you'll have to go here manually:
http://www.access.gpo.gov/nara/cfr/waisidx_07/21cfr133_07.html