The following will break on files containing newlines, but should work the rest of the time. It will sort the files based on the time they were last modified, rather than their actual creation time, because Ubuntu doesn't store the creation time of files. So if you've modified the files since you downloaded them, you won't get an accurate ordering.

n=0; ls -tr | while read i; do n=$((n+1)); mv -- "$i" "$(printf '%03d' "$n")"_"$i"; done

ls -tr sorts files by modification time, oldest first (and when you pipe the output of ls it automatically lists files one-per-line rather than the standard way of doing things -- it should be noted that this is a GNU-ism, if you have to work on another *nix with a different version of ls, this might not be the case). while read i takes that list and goes over each item one at a time, and the rest of it does the actual renaming.

n=$((n+1)) increments the variable $n by one. There could be problems if this had been set beforehand, so to be on the safe side you should set it to 0 at the beginning of the line.

$(printf '%03d' "$n") prints the number contained in the variable $n, padded to three zeros (so 001, 002 ... 087 ... 999). I hope that the mv command is fairly obvious.