How does produce grading in the US work?
Is everything graded on the same scale (with the same labels)? 


No.  Grading is specific to every kind of fruit or vegetable, and often grading can be different depending on the form of the produce (fresh vs. canned vs. frozen vs. juice vs. headed for further processing, etc.).  

Also, different nomenclature is used for different produce: some use "Grade A," "Grade B," etc.  Some use "No. 1," "No. 2," etc.  The number of grades can vary.  And some use other nomenclature like "Fancy Grade" or "Commercial Grade," either by themselves or in combination with the numerical/letter grade system.


And is all produce graded, so that for example I can go to the store and find out what grade their supply of a given fruit is?


Grading is voluntary, and it generally costs producers to do it.  Unless there is a complaint about quality, many domestic producers won't bother, particularly if they are selling at a local market or something.  For marketing agreements, they are often required, though.  And international shipments are required to be graded, but only small samples from a given shipment are generally inspected.


What characteristics do the grades generally depend on, and what characteristics do they ignore?


You really can only tell by reading the individual grading policies for specific produce (there are guidelines for well over 100 different types/forms of fruits and vegetables).  The guidelines for fruits are here and for vegetables are here.  Also, note that these are only national USDA guidelines.  States and regional markets can also set their own grading policies, so a "medium" tomato sold at a state farmers market might be the same as an "X-large" tomato on the USDA grading scale.

But in general, grading often covers things like:


Size (sometimes specifying different size grades or minimum size for grading)
Appearance (color, shape, "mature" enough to ensure proper ripening if not ripe already, proper trimming if applicable, extraneous pieces like stems on small fruit, etc.)
Texture (firmness, smoothness, general "ripe" characteristics, etc.)
Defects (blemishes, dirt, decay/spoilage, pest damage/disease, damage from sun/heat or cold, foreign material, etc.)
Allowable tolerances (allowed deviation levels in above characteristics or percentage of pieces allowed to be non-compliant in various characteristics)


Characteristics generally NOT covered by grading:


Flavor/taste
Interior of produce (since grading generally focuses on exterior inspection unless there is suspicion of unseen rot, disease, etc.)
Packaging (beyond some note of packing that is likely to damage produce)