With an infinite set of cubes, even the frustum has an infinite number of them. If someone has a better idea I am very interested to hear it. However, the octrees that you mention have worked wonderfully for me in the past. Basically any hierarchical structure will let you quickly eliminate huge number of objects. Then you can chose, depending on the complexity of the objects, whether you want to process all objects within an octtree node, or do you want to do finer detection which objects are within the frustum.
When you talk about cubes, I have a feeling you are talking about some kind of Minecraft like or voxel terrain. The frustum test is an important step, however do notice that in terrain case (and some others) you will have a great deal of objects (cubes) hidden "under" the visible ones. Finding a way to cull those efficiently will be of great importance. My point is that you should not spend every last CPU cycle frustum culling. If you can spend 20% of the time to frustum cull 80%, and then another 20% to cull 80% of hidden ones, it will be bigger improvement then to perform perfect frustum cull.
There are several ways of dealing with an infinite terrain.
1) If the terrain starts simple or small, but then grows, the octree should be balancing. This means that as you add more nodes into the tree, when a particular subtree grows beyond some threshold, one or more children should be pushed up or to the neighbouring tree. The idea is to try at all times have the (roughly) same number of subnodes in each subtree. This is a complex task, so you should definitely look for libraries rather then reinventing it yourself. It is worth noting that in most cases you do not need this complexity as it can be avoided using next method.
2) The easiest way to deal with seemingly "infinite" scene is to use two methods. A higher level structure that basically divides a terrain into a grid. Each grid location, chunk or area is a cube comrised of say 1000x1000x1000 of your cubes. Then use an octree to organize these 1024x1024x1024 area. Since you know the geometry of the large cube, it is easy to organize the octree. When rendering, you can use simple math to come up with several (10-is) large grid chunks that are in the frustum, and then process each one as a separate octree.