Pine (and its popular text editor, Pico), are not Free Software, and carry a restrictive software license that forbids distribution of modified binaries. Thus, it's illegal for Debian to include a "Debianized" Pine in binary form. Debian DOES include the source neccessary to do this, and it's not a big procedure.

Here's what to do:
(All this should be done as root)

1. Make sure the common development tools are installed:
make, gcc, etc.

You'll also need the package dpkg-dev installed.

2. Install the following packages:
pine-docs, pine396-src, pine396-diffs.

With APT configured, you can do this:

apt-get install pine-docs pine396-src pine396-diffs

3. Once all three packages are fully installed, go to /usr/src/pine. There's a README file there, consult it if you have any problems.

4. As stated (somewhat indirectly) in the README file, issue this command in the /usr/src/pine directory:

dpkg-source -x *.dsc

5. When that's done, switch to the pine-3.96M directory:

cd ./pine-3.96M

6. Execute this command (as root)

./debian/rules binary

7. Read the warning message, and press enter. Watch it compile, or go get coffee. It took about 10 minutes to compile on my P2/233.

8. cd back to /usr/src/pine, and check the directory listing

9. VIOLA!!! Four nice, shiny .deb files. You should know what to do from here. If not, here's what you want to do toinstall Pine and Pico:

dpkg -i /usr/src/pine/*.deb

COMMAND SUMMARY

su
IF THE DEVELOPMENT PACKAGES ARE NOT INSTALLED:
apt-get install make gcc dpkg-dev

The above line only applies if any of the development packages aren't already installed
apt-get install pine-docs pine396-src pine396-diff

cd /usr/src/pine
dpkg-source -x *.dsc
cd ./pine-3.96M
./debian/rules binary

You'll need to wait a while here, until the compile is done
dpkg -i /usr/src/pine/*.deb

Now, you can start Pine or Pico anytime with the following commands:
pine
pico