To locate the cell that contains a given node, I'd suggest using an AABB-Tree (see introduction in ). There is an implementation in the Geogram library  that I'm developping. There is also one in CGAL  (if you love C++ templates).
Once you have located the cell that contains the point, trilinear interpolation (as you suggest) is quite easy to implement (and efficient, does not cost a lot in terms of computation). In general, locating the cell that contains the point dominates computation time.
Edit (one more thought): if the border of your cell is decomposed into triangles (as it seems to be since you got 12 faces per cell), then, to have an interpolation that is coherent with your geometry, it may make more sense to (virtually) decompose the cells into tetrahedra, determine the tetrahedron that contains the point and do linear interpolation in it. It costs more than trilinear interpolation, but trilinear interpolation supposes that faces are bi-linear quads (instead of pairs of linear triangles).