Python, 324 chars, score = 319
---

    f=0xf
    x=0x12413624725935836a45647b48d58c59e69d6af78989abcdcdedef
    Z=[(x>>12*i&f,x>>12*i+4&f,x>>12*i+8&f)for i in range(18)]
    M=[[65532,'']]
    for i in' '*13:
     Q=[]
     for p,m in M:
      for a,b,c in[x[::-1]for x in Z]+Z:
       if p>>a&p>>b&~p>>c&1:Q+=[[p^2**a^2**b^2**c,m+"Peg %d jumps Peg %d to Hole %d.\n"%(a,b,c)]]
     M=Q
    print M[0][1]

The peg state is kept as a bitmask.  `M` contains a list of peg states and the instructions to get to that state.

I could make it print out all of the solutions as well (there are 29760 of them), but it would cost more than 10 characters to do it.

I can't post it on ideone as it takes about 90 seconds to run.

Output:


    Peg 6 jumps Peg 3 to Hole 1.
    Peg 4 jumps Peg 5 to Hole 6.
    Peg 1 jumps Peg 2 to Hole 4.
    Peg 14 jumps Peg 9 to Hole 5.
    Peg 12 jumps Peg 13 to Hole 14.
    Peg 7 jumps Peg 8 to Hole 9.
    Peg 10 jumps Peg 6 to Hole 3.
    Peg 4 jumps Peg 5 to Hole 6.
    Peg 3 jumps Peg 6 to Hole 10.
    Peg 15 jumps Peg 10 to Hole 6.
    Peg 6 jumps Peg 9 to Hole 13.
    Peg 14 jumps Peg 13 to Hole 12.
    Peg 11 jumps Peg 12 to Hole 13.