• KDE >= 3.2 - KDE is the great window manager, the powerful desktop, the very powerful c++ library K3b is based on, and a lot of programs.
• QT >= 3.2 KDE 3.2 requires the QT library version 3.2, a cross-platform GUI development toolkit. Since K3b is a threaded application QT needs to be compiled with threading support enabled.
• cdrecord/mkisofs - Cdrecord creates home-burned CDs with a CD-R/CD-RW recorder.
• dvd+rw-tools - The DVD+RW-Tools are used to burn and format DVD+R(W) and DVD-R(W) media. To enable all K3b DVD burning features version >= 7.0 is required.

Optionally:

• cdrdao - Cdrdao records audio or data CD-Rs in disk-at-once (DAO) mode based on a textual description of the CD contents (toc-file).
• MAD MPEG Audio Decoder Library - MAD is a high-quality MPEG audio decoder. It currently supports MPEG-1 and the MPEG-2 extension to lower sampling frequencies, as well as the de facto MPEG 2.5 format. All three audio layers - Layer I, Layer II, and Layer III (i.e. MP3) - are fully implemented.
  Used by the Mp3 decoding plugin.
• cdparanoia devel - Cdparanoia is a Compact Disc Digital Audio (CDDA) extraction tool, commonly known on the net as a 'ripper'.
• transcode - transcode is a linux text-console utility for video stream processing.
• Ogg Vorbis library - Ogg Vorbis is a completely open, patent-free, professional audio encoding and streaming technology with all the benefits of Open Source.
  Used by the Ogg Vorbis decoding and encoding plugins.
• FLAC++ library - FLAC stands for Free Lossless Audio Codec. Grossly oversimplified, FLAC is similar to MP3, but lossless, meaning that audio is compressed in FLAC without any loss in quality. This is similar to how Zip works, except with FLAC you will get much better compression because it is designed specifically for audio, and you can play back compressed FLAC files in your favorite player (or your car or home stereo, see links to the right for supported devices) just like you would an MP3 file.
  Used by the FLAC decoding plugin.
• VCDImager - A full-featured mastering suite for authoring, disassembling and analyzing Video CD's and Super Video CD's.
• Normalize - normalize is a tool for adjusting the volume of audio files to a standard level. This is useful for things like creating mixed CD's and mp3 collections, where different recording levels on different albums can cause the volume to vary greatly from song to song.
• eMovix - eMoviX is a tiny Linux CD distribution containing all the software to boot from a CD and play automatically every video file localized in the CD root.
• SoX - SoX is the swiss army knife of sound processing programs. SoX is a command line utility that can convert various formats of computer audio files in to other formats.
  Used by the SoX audio encoding plugin.
• Lame - LAME is an LGPL MP3 encoder. The Open source development model allowed to improve its quality and speed since 1999. It is now an highly evolved MP3 encoder, with quality and speed able to rival state of the art commercial encoders.
  Used by the external audio encoding plugin.
• Musepack (libmpcdec) - Musepack is an audio compression format with a strong emphasis on high quality. It's not lossless, but it is designed for transparency, so that you won't be able to hear differences between the original wave file and the much smaller MPC file.
  Used by the Musepack audio decoding plugin.
• libsndfile - Libsndfile is a C library for reading and writing files containing sampled sound (such as MS Windows WAV and the Apple/SGI AIFF format) through one standard library interface.
  Used by the libsndfile audio decoding plugin.
• ffmpeg - FFmpeg is a complete solution to record, convert and stream audio and video. It includes libavcodec, the leading audio/video codec library. FFmpeg is developed under Linux, but it can compiled under most operating systems, including Windows.
  Use by the ffmpeg audio decoding plugin.
• Musicbrainz (libmusicbrainz) - The MusicBrainz client library (also referred to as mb_client and libmusicbrainz) is a development library geared towards developers who wish to add MusicBrainz lookup capabilities to their applications.
  MusicBrainz is a user-maintained community music metadatabase. Music metadata is information such as the ArtistName, the AlbumTitle, and the list of tracks that appear on an album.
  Use by K3b to automatically fill in CD-Text information in an audio CD project.
• HAL - HAL is a piece of software that provides a view of the various hardware attached to a system. In addition to this, HAL keeps detailed metadata for each piece of hardware and provide hooks such that system- and desktop-level software can react to changes in the hardware configuration in order to maintain system policy.
  Using HAL K3b is able to add and remove devices while running (for example usb or firewire devices that are turned on while K3b is running).

• KDE >= 3.1.4 - KDE is the great window manager, the powerful desktop, the very powerful c++ library K3b is based on, and a lot of programs.
• QT >= 3.1 KDE 3.1.x requires the QT library version 3.1, a cross-platform GUI development toolkit. Since K3b is a threaded application QT needs to be compiled with threading support enabled.
• cdrecord/mkisofs - Cdrecord creates home-burned CDs with a CD-R/CD-RW recorder.
• dvd+rw-tools - The DVD+RW-Tools are used to burn and format DVD+R(W) and DVD-R(W) media. For DVD+R Double Layer burning version >= 5.20.4.10.8 is required.

Optionally:

• cdrdao - Cdrdao records audio or data CD-Rs in disk-at-once (DAO) mode based on a textual description of the CD contents (toc-file).
• MAD MPEG Audio Decoder Library - MAD is a high-quality MPEG audio decoder. It currently supports MPEG-1 and the MPEG-2 extension to lower sampling frequencies, as well as the de facto MPEG 2.5 format. All three audio layers - Layer I, Layer II, and Layer III (i.e. MP3) - are fully implemented.
  Used by the Mp3 decoding plugin.
• cdparanoia devel - Cdparanoia is a Compact Disc Digital Audio (CDDA) extraction tool, commonly known on the net as a 'ripper'.
• transcode - transcode is a linux text-console utility for video stream processing.
• Ogg Vorbis library - Ogg Vorbis is a completely open, patent-free, professional audio encoding and streaming technology with all the benefits of Open Source.
  Used by the Ogg Vorbis decoding and encoding plugins.
• FLAC++ library - FLAC stands for Free Lossless Audio Codec. Grossly oversimplified, FLAC is similar to MP3, but lossless, meaning that audio is compressed in FLAC without any loss in quality. This is similar to how Zip works, except with FLAC you will get much better compression because it is designed specifically for audio, and you can play back compressed FLAC files in your favorite player (or your car or home stereo, see links to the right for supported devices) just like you would an MP3 file.
  Used by the FLAC decoding plugin.
• VCDImager - A full-featured mastering suite for authoring, disassembling and analyzing Video CD's and Super Video CD's.
• Normalize - normalize is a tool for adjusting the volume of audio files to a standard level. This is useful for things like creating mixed CD's and mp3 collections, where different recording levels on different albums can cause the volume to vary greatly from song to song.
• eMovix - eMoviX is a tiny Linux CD distribution containing all the software to boot from a CD and play automatically every video file localized in the CD root.
• SoX - SoX is the swiss army knife of sound processing programs. SoX is a command line utility that can convert various formats of computer audio files in to other formats.
  Used by the SoX audio encoding plugin.
• Lame - LAME is an LGPL MP3 encoder. The Open source development model allowed to improve its quality and speed since 1999. It is now an highly evolved MP3 encoder, with quality and speed able to rival state of the art commercial encoders.
  Used by the external audio encoding plugin.

(Descriptions taken from the programs' web-pages)
(Please always use the latest versions!)
(Most of the packages should be part of every common linux distribution.)