Simplify complex hash-table manipulations in Common Lisp
First of all, I suggest that you use a structure instead of a hash table when you know that the table will only have 3 elements; this improves both readability and performance:

(defstruct triplestore-graph 
  (spo (make-hash-table))
  (pos (make-hash-table))
  (osp (make-hash-table)))
(defvar *triplestore-graph* (make-triplestore-graph))


Next, there is no puthash in Common Lisp, use (setf gethash) instead.

Finally, I would modify the code like this:

(defun triplestore-add (s p o)
  (triplestore-add-to-index (triplestore-graph-spo *triplestore-graph*) s p o)
  (triplestore-add-to-index (triplestore-graph-pos *triplestore-graph*) p o s)
  (triplestore-add-to-index (triplestore-graph-osp *triplestore-graph*) o p s)) ; o s p?!

(defun triplestore-add-to-index (index a b c)
  (let ((at (gethash a index)))
    (if at
        (pushnew c (gethash b at))
        (setf (gethash a index)
              (let ((tmp (make-hash-table)))
                (setf (gethash b tmp) (list c))
                tmp)))))