You're almost all the way there: just move the $1 to the end of the replacement string. Also, it'll be a little easier if you take the greater than (>) out of the match.
Code:
perl -p -e 's/^>(.*)/>New_Header_Info $1/' input.fasta > output.fasta
For this, you really don't need the /g at the end since you're matching the whole line and, because the .* is greedy, the $ at the end of the match string is unnecessary as well.