The easiest way is to buy yourself a 3D camera.

This option has an excellent advantage: You can see the 3D effect while you compose and when reviewing your images which lets you know if the shot you take worked to give the 3D impression or not.

Otherwise you have to take 2 nearly identical photos with slightly different viewpoints. There are three methods to do this:

• Take a photo, move the camera and take a second photo keeping everything constant: Focus, DOF, exposure, ISO, white-balance. This is easier to do with a camera with manual controls, although I suspect you can use Panorama Assist mode of compact-cameras too. They key is to move the camera along a level path a relatively small distance. The ideal distance between the two shots depends on focal-length, focus distance and desired perspective.
• Take two photos simultaneously: Get two identical cameras and set everything including focus distance and focal-length to exactly the same settings. Triggering them simultaneously using an IR remote is ideal. You can get away with mechanically triggering them if there are no movements in the scene. You can buy a dual tripod plate which can hold two cameras to help with this.
• Use an anamorphic 3D lens: These lenses capture two images side-by-side on your sensor. You need special software (supplied with cameras that support this lens) to transform the resulting image into an actual 3D image.

The distance between the two shots has to be such that the objects in the plane of focus appear slightly different but not too much. There is no ideal distance. The further the subject you are trying to focus on appears, the wider apart the pictures must be taken. This should take into consideration actual distance and focal-length, so longer a focal-length requires less movement between the shots.

You can view these images, which are actually stereoscopic images, by various means:

• Many new HDTV support 3D HDMI input which you can see using special glasses (not red-blue). Some display can also display the 3D effect without viewing glasses as long as you are standing with a certain distance and angle from the screen.
• You can have your images on paper using lenticular printing services. See this question.
• Get a 3D Digital photo frame.

The software you need depends on your viewing device. If you have a 3D display device you have to make sure which format they use. So far, the MPO format is most popular, although Stereo JPEG (JPS) images exist. Fuji has software to convert between MPO and pairs of JPEGs. A number of free utilities exist but I have not much experience with them.