How can I apply textures without them stretching?
UV Mapping
A 3D model is usually made by a bunch of faces in the 3D space. Textures are 2D images. UV Mapping defines how the images cover the model
Imagine that you have to peel of the surface of an object and to put it on a table: if you object is a cube, it will not be a difficoult task, you'll just have to cut along some of the edges (the Seams) and unfold it. But if your object is curved, things became less obiouvs even with simple objects ( for example a sphere).
You can have a visual explanation in this video introduction about the topic.  Here's an extract :


As written in the Blender's reference manual page:

Every point in the UV map corresponds to a vertex in the mesh. The lines joining the UVs correspond to edges in the mesh. Each face in the UV map corresponds to a mesh face...
...When you unwrap a face to a UV Texture in the UV/Image Editor, each face of the mesh is automatically assigned four UV coordinates: These coordinates define the way an image or a texture is mapped onto the face.

So if you have a no UVmap assigned, the texture will not be mapped.
If you have a basic UV unwrap (like the one you get from UV mappaing (U in Edit mode) and choosing Reset option) each face will show all the texture, resulting in the repeating pattern shown below:

As the faces are long thin rectangles and the image is squared, the applied texture looks distorted (scaled on th z axis).
Let's modify the uv mapping a bit
Start from marking the top and bottom edge rings and one of the vertical edges as Seams.

Notice that the edge marked as Seams are now drawn with a red highlites to be distingushed from the others. They corrispond to the edges where the UV island's edges can be splitted,
Now, by running the UV mapping command and choosing the Unwrap option and scaling the island, you can get the following result:

UV mapping is a complex task that requires lot of practice to be mastered; there are many ways in which a group of faces can be unwrapped and Blender has many different tools to help you (you can find more info by examining the link to the manual at the beginning).
You can also have a look at the following videotutorials:

Blender: Uv Unwrapping a Curved Mesh
Blender Tutorial - UV Unwrapping basics for Texturing
Call for help - UV Unwrapping Slightly Complex Objects In Blender &amp; Other UV Tricks
...

Basically any object that has texture needs a correct unwrap, so you'll find a section about it everywhere.
In the UVImage editor there is a checkbox that can help you to examine the streching of your uv island:

In the example above the circles on top are the UV island of the bottom and top faces of the cylinder. Their blue colour means there is no stretch. On the other hand the Side face's UV island has a gradient because the unwrapping was made without marking enough seams.
In this particular case I didn't set any vertical seams, so the peeled surface is a ring. A ring can be flattened upon a table, but you'll have to stretch a bit the material (inner fibers are compressed and outer are in traction) by twisting it.

Obiuvsly seams are not the answer for every problem. Where there is a seam, you'll have a discontinuity if your texture is not seamsless. Depending on what is the purpose, you'll have to find an equilibrium point between seams (discontinuity) and streching (distortion).
Procedural textures don't need unwrap because are mathemathically defined in the 3D space.