Use 'dpkg -L gcc' to see what files that package installed, then make sure the directory the gcc binary is in is in your PATH variable.
Code:
cromagnon@box:~$ dpkg -L gcc
/.
/usr
/usr/bin
/usr/bin/c89
/usr/bin/c99
/usr/share
/usr/share/man
/usr/share/man/man1
/usr/share/man/man1/c89.1.gz
/usr/share/man/man1/c99.1.gz
/usr/share/doc
/usr/share/doc/cpp
/usr/bin/gcov
/usr/bin/gccbug
/usr/bin/i386-linux-gcc
/usr/bin/gcc
/usr/share/man/man1/gcov.1.gz
/usr/share/man/man1/gccbug.1.gz
/usr/share/man/man1/i386-linux-gcc.1.gz
/usr/share/man/man1/gcc.1.gz
/usr/share/doc/cpp/README.Bugs
/usr/share/doc/cpp/FAQ.gz
/usr/share/doc/cpp/cpp
/usr/share/doc/gcc