Base85 Encoding

CJam, 43 39 35 bytes

"<~"q4/{:N4Ue]256b85b'!f+}/N,)<"~>"

Try it online in the CJam interpreter.

How it works

"<~"      e# Push that string.
q4/       e# Read all input from STDIN and split it into chunks of length 4.
{         e# For each chunk:
  :N      e#   Save it in N.
  4Ue]    e#   Right-pad it with 0's to a length of 4.
  256b85b e#   Convert from base 256 to base 85.
  '!f+    e#   Add '!' to each base-85 digit.
}/        e#
N,)       e# Push the length of the last unpadded chunk, plus 1.
<         e# Keep that many chars of the last encoded chunk.
"~>"      e# Push that string.

If the input was empty, N,) will apply to the string "<~". Since N initially holds a single character, the output will be correct.

We don't have to deal with z or pad the encoded chunks to length 5, since the input will contain only printable ASCII characters.

Python 3, 71 bytes

from base64 import*
print(a85encode(input().encode(),adobe=1).decode())

I've never golfed in Python, so this is probably sub-optimal.

Thanks to @ZachGates for golfing off 3 bytes!

Pure bash, ~738

Encoder first (something golfed):

#!/bin/bash
# Ascii 85 encoder bash script
LANG=C

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~;l()
{ q=$(($1<<24|$2<<16|$3<<8|$4));q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1
}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}";};k() { ((${#p}>74))&&ech\
o "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{ print\
f -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||
o+=(0);((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&& q=z|| l ${o[@]};p+="${q}";k
o=(); };done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));};((f==0))&&[ \
"${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&e\
cho "$p"

Tests:

for word in easy test code\ golf Programming\ Puzzles ;do
    printf "    %-24s %s\n" "$word:" $(./enc85.sh < <(printf "$word"))
  done
    easy:                   <~ARTY*~>
    test:                   <~FCfN8~>
    code golf:              <~@rGmh+D5V/Ac~>
    Programming Puzzles:    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>

and decoder now:

#!/bin/bash
# Ascii 85 decoder bash script
LANG=C

printf -v n "\%o" {33..117};printf -v n "$n";o=1 k=1;j(){ read -r q||o=;[ "$q" \
]&&[ -z "${q//*<~*}" ]&&((k))&&k= q="${q#*<~}";m+="$q";m="${m%~>*}";};l(){ r=;f\
or((i=0;i<${#1};i++)){ s="${1:i:1}";case "$s" in "*"|\\|\?)s=\\${s};;esac;s="${\
n%${s}*}";((r+=${#s}*(85**(4-i))));};printf -v p "\%03o" $((r>>24)) $((r>>16&255
)) $((r>>8&255)) $((r&255));};for((;(o+${#m})>0;)){ [ "$m" ] || j;while [ "${m:0
:1}" = "z" ];do m=${m:1};printf "\0\0\0\0";done;if [ ${#m} -ge 5 ];then q="${m:0
:5}";m=${m:5};l "$q";printf "$p";elif ((o));then j;elif [ "${m##z*}" ];then pri\
ntf -v t %$((5-${#m}))s;l "$m${t// /u}";printf "${p:0:16-4*${#t}}";m=;fi;}

Copy this in enc85.sh and dec85.sh, chmod +x {enc,dec}85.sh, then:

for string in 'ARTY*' 'FCfN8' '@rGmh+D5V/Ac' ':i^JeEa`g%Bl7Q+:j%)1Ch7Y' ;do
    printf "    %-42s %s\n" "<~$string~>:" "$(./dec85.sh <<<"<~$string~>")"
  done
    <~ARTY*~>:                                 easy
    <~FCfN8~>:                                 test
    <~@rGmh+D5V/Ac~>:                          code golf
    <~:i^JeEa`g%Bl7Q+:j%)1Ch7Y~>:              Programming Puzzles

./enc85.sh <<<'Hello world!'
<~87cURD]j7BEbo80$3~>
./dec85.sh <<<'<~87cURD]j7BEbo80$3~>'
Hello world!

But you could do some stronger test:

ls -ltr --color $HOME/* | gzip | ./enc85.sh | ./dec85.sh | gunzip

Reduced to 724 chars:

printf -v n \\%o {32..126};printf -v n "$n";printf -v m %-20sE abtnvfr;p=\<~
l(){ q=$(($1<<24|$2<<16|$3<<8|$4))
q="${n:1+(q/64#378iN)%85:1}${n:1+(q/614125)%85:1}${n:1+(q/7225)%85:1}${n:1+(q/85)%85:1}${n:1+q%85:1}"
};k() { ((${#p}>74))&&echo "${p:0:75}" && p=${p:75};};while IFS= read -rd '' -n 1 q;do [ "$q" ]&&{
printf -v q "%q" "$q";case ${#q} in 1|2)q=${n%$q*};o+=($((${#q}+32)));;7)q=${q#*\'\\}
o+=($((8#${q%\'})));;5)q=${q#*\'\\};q=${m%${q%\'}*};o+=($((${#q}+07)));;esac;}||o+=(0)
((${#o[@]}>3))&&{ [ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q}";k
o=();};done;[ "$o" ]&&{ f=0;for((;${#o[@]}<4;)){ o+=(0);((f++));}
((f==0))&&[ "${o[*]}" = "0 0 0 0" ]&&q=z||l ${o[@]};p+="${q:0:5-f}";};p+="~>";k;[ "$p" ]&&echo "$p"