Finding node paths

def findnodepaths(nodepaths, graph, *nodes):

By python convention, you should really separate the words with underscores. i.e. find_node_paths. I'd also wonder if it makes sense to take *nodes, rather then expecting a list to be sent in.

# nodepaths == list()

Its not clear why you pass this in, rather then just make it here

# graph == defaultdict(set)
# *nodes == 'foo','bar',... possible items in the graph

This sort of documentation should be in a doctoring, not comments

    nodeset = set(nodes) & set(graph.keys())

set(graph.keys()) == set(graph), although you may prefer to be explicit.

# nodeset == nodes that are in the graph ... avoids try / if 

    nodepaths = [(nodeA,weight,nodeB) for nodeA in nodeset for (nodeB,weight) in graph[nodeA]]

I'd store a path as a list, not a tuple.

    for path in nodepaths:
# for every item in list

That's not a very helpful comment, the syntax already told me that.

        *xs, nodeA = path
# nodeA == last value added, xs == all the rest

consider renaming your variable rather then using comments

        for (nodeB,weight) in graph[nodeA]:

Parens are unnecessary

# search again ... just like we all ready have

Again, noisy comment

            if nodeB not in xs:
# if new val not in the triple / quadruple ...
                nodepaths.append( path + (weight,nodeB) )

You shouldn't be modifying lists currently having a for loop operating on them. Its considered bad style

# add new item to list based on its match
# repeat until no new paths can be found

    return nodeset, nodepaths
# return nodes that were found + all of their paths

I'd write this as a recursive function:

def _findnodepaths(graph, path, weights):
    for node, weight in graph[path[-1]]:
        if node not in path:
            yield _findnodepaths(graph, path + [node], weights + [node])
    yield path

def findnodepaths(graph, nodes):
    nodeset = set(nodes) & set(graph)
    subgraph = dict( (key, value) for key, value in graph.items())

    nodepaths = []
    for key in graph:
        nodepaths.extend(_findnodepaths(subgraph, [key], [])
    return nodeset, node paths

Whether that's better or not is subjective, I think it shows the algorithm better.