The permeability of natural porous media, such as soils and rocks, usually possesses uncertainties due to the randomness and spatial variation of microscopic pore structures. It is of great importance to develop an effective methodology to obtain statistical properties of permeability for porous media. In this work, an efficient approach is developed by combining the sphere packing algorithm, lattice Boltzmann method (LBM), and probabilistic collocation method (PCM). The porous media are generated by sphere packings of a specified size distribution, and the isotropy and representative elementary volume are verified by statistical analyses. Fluid flow in the complex pore structures is numerically resolved by LBM, with the permeability calculated by Darcy's law. The uncertainty of permeability can be quantified by PCM with only several porosity samplings required at predetermined collocation points. In addition, the porosity-permeability relationships can be acquired efficiently. Numerical results indicate that, with the proposed approach, the computational efforts are reduced by more than two orders of magnitude compared to the Monte Carlo simulations.