A simple rule of thumb is, when you're talking about a noun that has a restrictive clause on it, use 'the'; if you're talking about an unrestricted noun, don't use 'the'.
An "unrestricted noun" talks about an entire group; a noun with a restrictive clause talks only about some subset of the group.
In your first example, "Americans" is an unrestricted noun: it refers to every American citizen. So, you can leave off "the":
22% of Americans want Bruce Springsteen to write a new national anthem.
In your second example, the noun is "times", but it has the restrictive clause "[that] I lie down"; we are not talking about all times, only a specific subset of them. So we want to use 'the' in this case:
25% of the times I lie down, I fall asleep.
Of course, having laid out this rule of thumb, I feel compelled to point out some exceptions. First, when you use a noun that is understood to be part of some larger group, even though it's not explicitly stated, you still use 'the':
Everybody here is hungry, and most of us have agreed to order pizza, but 40% of the Americans are holding out for cheeseburgers.
Secondly, time almost always takes 'the':
How often do I fall asleep when I lie down? Oh, about 25% of the time.
This is probably because it is implicitly restricted by the conditions in the question, although those conditions are not repeated in the answer.
(The use of all, while not strictly incorrect, is redundant and unnecessary.)