Refactor deeply nested if-else
Set args = (int(s != None), int(p != None), int(o != None)) [or args = ''.join(map(str, (int(s != None), int(p != None), int(o != None))))]

Now args will be (1, 0, 1) [or '101'] if p is None and the other two aren't.
Also, instead of using for loops you can use generator expressions to make the code more concise.




def triples(self, (s, p, o)):
    try:
        args = (int(s != None), int(p != None), int(o != None))
        if args == (1, 1, 1):
            #if o in self._spo[s][p]: #See sindikat's comment below
            #   yield (s, p, o)
            return iter([(s, p, o)] if o in self._spo[s][p] else [])
        if args == (1, 1, 0):
            return ((s, p, ro) for ro in self._spo[s][p])
        if args == (1, 0, 1):
            return ((s, rp, o) for rp in self._osp[o][s])
        if args == (1, 0, 0):
            return ((s, rp, ro) for rp, oset in self._spo[s].items() for ro in oset)
        if args == (0, 1, 1):
            return ((rs, p, o) for rs in self._pos[p][o])
        if args == (0, 1, 0):
            return ((rs, p, ro) for ro, sset in self._pos[p].items() for rs in sset)
        if args == (0, 0, 1):
            return ((rs, rp, o) for rs, pset in self._osp[o].items() for rp in pset)
        if args == (0, 0, 0):
            return ((rs, rp, ro) for rs, pset in self._spo.items() for rp, oset in pset.items() for ro in oset)
    except KeyError:
        pass


Combining this with Winston's suggestion you get the following definition

def triples(self, (s, p, o)):
    try:
        args = (int(s != None), int(p != None), int(o != None))

        if args in [(1, 1, 1), (1, 1, 0), (1, 0, 0), (0, 0, 0)]:
            lookat  = self._spo
            a1 = s; a2 = p; a3 = o;
            invperm = [0, 1, 2]
        if args in [(0, 1, 1), (0, 1, 0)]:
            lookat = self._pos
            a1 = p; a2 = o; a3 = s;
            invperm = [2, 0, 1]
        if args in [(1, 0, 1), (0, 0, 1)]:
            lookat = self._osp
            a1 = o; a2 = s; a3 = p;
            invperm = [1, 2, 0]

        permute = lambda x, p: (x[p[0]], x[p[1]], x[p[2]])

        if sum(args) == 3:
            #if a3 in lookat[a1][a2]: #See sindikat's comment below
            #   yield permute((a1, a2, a3), invperm)
            return iter([permute((a1, a2, a3), invperm)] if a3 in lookat[a1][a2] else [])
        if sum(args) == 2:
            return (permute((a1, a2, ra3), invperm) for ra3 in lookat[a1][a2])
        if sum(args) == 1:
            return (permute((a1, ra2, ra3), invperm) for ra2, a3set in lookat[a1].items() for ra3 in a3set)
        if sum(args) == 0:
            return (permute((a1, a2, a3), invperm) for ra1, a2set in lookat.items() for ra2, a3set in a2set.items() for ra3 in a3set)
    except KeyError:
        pass


Although this is slightly longer, it is easier to maintain in the sense that if you feel that the dictionary to look at should be changed (for better performance) for some combination of input, then the modification is easily accomplished with the second definition.