What percentage of eligible voters participated in the recent US
presidential election and what was the percentage increase over the
2000 election?

For 2000, refer to

http://www.infoplease.com/ipa/A0781453.html

The percentage of eligible voters who voted was 51.3%
The percentage of registered voters who voted was 67.5%

For 2004, refer to

http://www.infoplease.com/ipa/A0922901.html

The total number of votes cast was 115.7 million. To get the number of
eligible voters, take the census data shown in the first reference
above for 1990-2000 and extrapolate to 2004. This gives 213.8 million
eligible voters in 2004. Alternatively, if you'd rather take the
Census Bureau's estimate:
 http://www.census.gov/Press-Release/www/releases/archives/facts_for_features_special_editions/002957.html

the number is 217.8 million. Well, let's believe the Census Bureau...

Then:

The percentage of eligible voters who voted was 53.1%
The percentage of registered voters who voted does not seem to be
available as yet--it probably hasn't been fully counted yet!

Now for the "percentage increase," I have to interpret what you want.
Literally, the percentage increase in the percentage voting is
(53.1-51.3)/51.3 = 3.5%.

If however, you want to know the increase in the number of votes cast,
it's (115.7-105.6)/105.6 = 9.6%. (The eligible voting population has
increased by an estimated 5.8%.)

These number are just a little bit slippery, depending on how reliable
you take the source data to be. For 2004, final counts may not be
complete, especially where provisional and absentee ballots are not
fully counted and validity of voter registration is not final.
Hopefully the 2000 numbers are a bit more reliable.