Here is a paraboloid I folded from elephant hide paper using a pattern from the book Folding Techniques for Designers by Paul Jackson.

It was quite simple - you just make two diagonal folds on a square piece of paper, then fold concentric squares alternating between valley and mountain folds.  The only difficulty was the thickness and size of the paper!