See if setting TERM to "putty" works. Assuming bash is your shell, do:
export TERM=putty
if this fixes things, you can configure PuTTY to send "putty" as its terminal string in PuTTY's menu. It's possible that the termcap entry for "putty" is old or doesn't work perfectly, but I think it should more or less work. You could also try xterm-color and xterm-xfree86, though technically you shouldn't use either of these.
Just so you know, a lot of times, page-up / page-down work on programs within the shell and shift page-up and shift page-down works on the terminal's scrollback buffer. That's how xterm works, and (IIRC) putty and SecureCRT as well. OS X's Terminal client works the opposite way. So if you're trying to page-up / page-down through the scrollback buffer, try using shift page-up / shift page-down.
You're seeing a tilde (and probably another character or two) because PuTTY is sending a control string which isn't recognized as a capability of your $TERM setting (probably xterm, which is what putty sends as its terminal string by default).