Many applications involve the flow of non-Newtonian fluids in porous, subsurface media including polymer flooding in enhanced oil recovery, proppant suspension in hydraulic fracturing, and the recovery of heavy oils. Network modeling of these flows has become the popular pore-scale approach for understanding first-principles flow behavior, but strong nonlinearities have prevented larger-scale modeling and more time-dependent simulations. We investigate numerical approaches to solving these nonlinear problems and show that the method of fixed-point iteration may diverge for shear-thinning fluids unless sufficient relaxation is used. It is also found that the optimal relaxation factor is exactly equal to the shear-thinning index for power-law fluids. When the optimal relaxation factor is employed it slightly outperforms Newton's method for power-law fluids. Newton-Raphson is a more efficient choice (than the commonly used fixed-point iteration) for solving the systems of equations associated with a yield stress. It is shown that iterative improvement of the guess values can improve convergence and speed of the solution. We also develop a new Newton algorithm (Variable Jacobian Method) for yield-stress flow which is orders of magnitude faster than either fixed-point iteration or the traditional Newton's method. Recent publications have suggested that minimum-path search algorithms for determining the threshold pressure gradient (e.g., invasion percolation with memory) greatly underestimate the true threshold gradient when compared to numerical solution of the flow equations. We compare the two approaches and reach the conclusion that this is incorrect; the threshold gradient obtained numerically is exactly the same as that found through a search of the minimum path of throat mobilization pressure drops. This fact can be proven mathematically; mass conservation is only preserved if the true threshold gradient is equal to that found by search algorithms.