Preferably from Ubuntu repositories.
Others have mentioned OProfile; for full-system statistical profiling on modern Linux installations, it does indeed rock.
The more venerable tool (which doesn't require kernel support and thus will work under older versions of Linux or even non-Linux operating systems) is GNU gprof, included in binutils (and thus doubtless already installed in your development environment).
To use gprof, just compile your application with the -pg argument to gcc; a file called gmon.out will be created after your program exits, and gprof can then be used to analyze this file.