I made some progress in answering my question.
Let A be the adjacency matrix for a directed graph G that contains n nodes. This is, of course, the general case, and whenever we speak of an undirected graph, that is taken as a shorthand for a directed graph with edges going in both directions.
Let T: R^n --> R^n be the linear transformation performed by A.
Let v in R^n be a vector whose components are natural numbers. So v represents a multiset of nodes in G. Then T(v) also has components that are natural numbers.
I.e., T maps N^n into N^n.
Now let's start by considering the interpretation of an eigenvector w in N^n. Since T(w) is in N^n, it must be that T(w) = q w, for some non-negative rational number q.
Let's take a further special case, where w1 is an eigenvector whose components are 0 or 1. Then T(w1) = k w, for some non-negative integer k.
w1 is the characteristic function for a subgraph G1 of G.
Hence, for any node i in G, T(w1)(i) = the number of predecessors that i has in G1.
Since w1 is an eigenvector with eigenvalue k, we also know that:
For any node i in G, T(w1)(i) = k if i is in G1, else it equals 0.
Putting these two statements together, it follows that:
So T(w1)(i) = the number of predecessors that i has in G1 = k if i is in G1, else 0.
Conclusion: the characteristic function a subgraph G1 is an eigenvector of T, with eigenvalue k, if and only if every node in G1 has exactly k predecessors in G1.
Let G' be the restriction of G to G1.
k = 0. Then for each node i in G1, all of the predecessors are outside of G1. That is to say, G' has no edges at all.
k = 1. Every node in G' has a single predecessor. Then G' is a union of finite cycles and/or infinite linear chains.
k = 2. Every node in G' has exactly two predecessors.
Example: an infinite binary tree, oriented with the edges coming into the root.
Example: an undirected graph that consists of linear chains and finite cycles.
k = 3.
Example: the cube, viewed as an undirected graph.
Example: an infinite hexagonal lattice, viewed as an undirected graph
In the world of undirected graphs, the characteristic functions for any subgraph in one of the following forms is an eigenvector:
* isolated points
* infinite chains
* regular polyhedron
* regular infinite lattice