The template is "forumjump", which is in the root of the templateview, but I think that you'll have to hack some code too.
Haven't found the right file to hack though.
Just open the include files and look for "forumjump" and i guess you'll find the one to alter.
Also, you could try
this thread. That will give you some hints were to look.
It's in forumdisplay.php near line 66.
I don't know how to add a link with a parameter though (like search.php?do=getnew) like you want, but maybe you can figur that one out.