CやC++の標準ライブラリは既に入っていると思います。
SDLのヘッダは「libsdl1.2-dev」パッケージで提供されています。パッケージ名の後ろにdevがつくものには、そのライブラリのヘッダなどが含まれています。

「linux getch」でネット検索すると、Windowsのgetchと同様の機能を実装する方法が多数ヒットすると思うので、参考にしてみてください。

SDLなどの標準でないライブラリを使う場合、コンパイラに引数を渡す必要があります。統合開発環境を利用すると、そのあたりの作業を自動的に行なったり、プログラムの雛形を作ってくれたりするので便利です。Ubuntuで利用できる有名な統合開発環境は、AnjutaやEclipseでしょうか。(予め環境が整っているという点ではAnjutaのほうが使いやすいかもしれません。)