Often cryptographic algorithms and protocols are necessary to keep a system secure, particularly when communicating through an untrusted network such as the Internet. Where possible, use session encryption to foil session hijacking and to hide authentication information, as well as to support privacy.
For background information and code, you should probably look at the classic text ``Applied Cryptography'' [Schneier 1996]. The newsgroup ``sci.crypt'' has a series of FAQ's; you can find them at many locations, including http://www.landfield.com/faqs/cryptography-faq. Linux-specific resources include the Linux Encryption HOWTO at http://marc.mutz.com/Encryption-HOWTO/. A discussion on how protocols use the basic algorithms can be found in [Opplinger 1998]. A useful collection of papers on how to apply cryptography in protocols can be found in [Stallings 1996]. What follows here is just a few comments; these areas are rather specialized and covered more thoroughly elsewhere.
It's worth noting that there are many legal hurdles involved with cryptographic algorithms. First, the use, export, and/or import of implementations of encryption algorithms are restricted in many countries. Second, a number of algorithms are patented; even if the owners permit ``free use'' at the moment, without a signed contract they can always change their minds later. Most of the patent issues can be easily avoided nowadays, once you know to watch out for it, so there's little reason to subject yourself to the problem.
Cryptographic protocols and algorithms are difficult to get right, so do not create your own. Instead, use existing protocols and algorithms where you can. In particular, do not create your own encryption algorithms unless you are an expert in cryptology, know what you're doing, and plan to spend years in professional review of the algorithm. Creating encryption algorithms (that are any good) is a task for experts only.
For protocols, try to use standard-conforming protocols such as SSL (soon to be TLS), SSH, IPSec, GnuPG/PGP, and Kerberos. Many of these overlap somewhat in functionality, but each has a ``specialty'' niche. SSL (soon to be TLS) is the primary method for protecting http (web) transactions. PGP-compatible protocols (implemented in PGP and GnuPG) are a primary method for securing email end-to-end. Kerberos is a primary method for securing and supporting authentication on a LAN. SSH is the primary method of securing ``remote terminals'' over an internet, e.g., telnet-like and X windows connections, though it's often used for securing other data streams too (such as CVS accesses). Note that there are two major versions of the SSH protocol, and there are several choices for key types and so on; see its documentation for more information. IPSec is the primary method for securing lower-level packets and ``all'' packets, so it's particularly useful for securing virtual private networks and remote machines. The new version of the Internet Protocol, IPv6, comes with IPSec ``built in,'' but IPSec also works with the more common IPv4 protocol.
For secret key (bulk data) encryption algorithms, use only encryption algorithms that have been openly published and withstood years of attack, and check on their patent status. For encrypting unimportant data, the old DES (56-bit key) algorithm still has some value, but with modern hardware it's too easy to break. For many applications triple-DES is currently the best encryption algorithm; it has a reasonably lengthy key (112 bits), no patent issues, and a long history of withstanding attacks. The AES algorithm may be worth using as well, once it's proven, and you should prepare to be able to switch to it (it's much faster than triple-DES). Twofish is another excellent encryption algorithm. You should avoid IDEA due to patent issues (it's subject to U.S. and European patents), but I'm unaware of any serious technical problems with it. Your protocol should support multiple encryption algorithms, anyway; that way, when an algorithm is broken, users can switch to another one.
For public key cryptography (used, among other things, for authentication and sending secret keys), there are only a few widely-deployed algorithms. One of the most widely-used algorithms is RSA; RSA's algorithm was patented, but only in the U.S., and that patent expired in September 2000. The Diffie-Hellman key exchange algorithm is widely used to permit two parties to agree on a session key. By itself it doesn't guarantee that the parties are who they say they are, or that there is no middleman, but it does strongly help defend against passive listeners; its patent expired in 1997. NIST developed the digital signature standard (DSS) (it's a modification of the ElGamal cryptosystem) for digital signature generation and verification; one of the conditions for its development was for it to be patent-free.
Some programs need a one-way hash algorithm, that is, a function that takes an ``arbitrary'' amount of data and generates a fixed-length number that hard to invert (e.g., it's difficult for an attacker to create a different set of data to generate that same value). For a number of years MD5 has been a favorite, but recent efforts have shown that its 128-bit length may not be enough [van Oorschot 1994] and that certain attacks weaken MD5's protection [Dobbertin 1996]. Indeed, there are rumors that a top industry cryptographer has broken MD5, but is bound by employee agreement to keep silent (see the Bugtraq 22 August 2000 posting by John Viega). Anyone can create a rumor, but enough weaknesses have been found that the idea of completing the break is plausible. If you're writing new code, you ought to use SHA-1 instead.
One issue not discussed often enough is the problem of ``traffic analysis.'' That is, even if messages are encrypted and the encryption is not broken, an adversary may learn a great deal just from the encrypted messages. For example, if the presidents of two companies start exchanging many encrypted email messages, it may suggest that the two comparies are considering a merger. For another example, many SSH implementations have been found to have a weakness in exchanging passwords: observers could look at packets and determine the length (or length range) of the password, even if they couldn't determine the password itself. They could also also determine other information about the password that significantly aided in breaking it.
In a related note, if you must create your own communication protocol, examine the problems of what's gone on before. Classics such as Bellovin [1989]'s review of security problems in the TCP/IP protocol suite might help you, as well as Bruce Schneier [1998] and Mudge's breaking of Microsoft's PPTP implementation and their follow-on work. Of course, be sure to give any new protocol widespread review, and reuse what you can.