Python, 130 points

The algorithm works by encoding each position in the board, one at a time, into a big integer. For each position, it calculates the possible values given all the assignments encoded so far. So if [1,3,7,9] are the possible values for a given position, it takes 2 bits to encode the choice.

The nice thing about this scheme is that if a position has only a single remaining choice, it takes no space to encode.

Once we have the big integer we write it out in base 95.

There are probably better encoding orderings than lexicographic, but I haven't thought a lot about it.

Encoder:

import sys

sets = [range(i*9, i*9+9) for i in xrange(9)]
sets += [range(i, 81, 9) for i in xrange(9)]
sets += [[i/3*27+i%3*3+j/3*9+j%3 for j in xrange(9)] for i in xrange(9)]

M = []
for line in sys.stdin.readlines():
    M += [int(x) for x in line.split()]

A = 0
m = 1
for i in xrange(81):
    allowed = set(xrange(1,10))
    for s in sets:
        if i in s:
            for j in s:
                if j < i: allowed.discard(M[j])
    allowed = sorted(allowed)
    A += m * allowed.index(M[i])
    m *= len(allowed)

s=''
while A != 0:
    s+='%c'%(32+A%95)
    A /= 95
print s

Decoder:

sets = [range(i*9, i*9+9) for i in xrange(9)]
sets += [range(i, 81, 9) for i in xrange(9)]
sets += [[i/3*27+i%3*3+j/3*9+j%3 for j in xrange(9)] for i in xrange(9)]

s=raw_input()
A=0
m=1
while s != '':
    A += m * (ord(s[0])-32)
    s = s[1:]
    m *= 95

M=[]
for i in xrange(81):
    allowed = set(xrange(1,10))
    for s in sets:
        if i in s:
            for j in s:
                if j < i: allowed.discard(M[j])
    allowed = sorted(allowed)
    M += [allowed[A%len(allowed)]]
    A /= len(allowed)

for i in xrange(9):
    print ' '.join(str(x) for x in M[i*9:i*9+9])

Run it like this:

> cat sudoku1 | ./sudokuEnc.py | ./sudokuDec.py
9 7 3 5 8 1 4 2 6
5 2 6 4 7 3 1 9 8
1 8 4 2 9 6 7 5 3
2 4 7 8 6 5 3 1 9
3 9 8 1 2 4 6 7 5
6 5 1 7 3 9 8 4 2
8 1 9 3 4 2 5 6 7
7 6 5 9 1 8 2 3 4
4 3 2 6 5 7 9 8 1