(*Revised*) Let me first answer your request for a reference, and then reply
to the three questions.
The most detailed proof of the One-Cut Theorem is in Chapter 17 of

*Geometric Folding Algorithms: Linkages, Origami, Polyhedra*.
Cambridge. 2007. (Book link).

Here is a challenging 2D example to fold from that chapter (red=mountain, green=valley):

(This one works best with a papercutter!)
Here is a link to this and other templates, suitable for classroom use.

**Q3**. (From my comment:) One can state a higher-dimensional analog, but no one has proven any result in three or higher dimensions.

**Q1 & Q2**.
These two questions (algorithmic complexity, combinatorial complexity) are two sides
of the same issue. Essentially, neither complexity question has been answered precisely.
However, in some sense the answers are known. The best source is the first paper
on the topic, which precedes the book reference above by a decade (and much was learned
in that decade):

Bern, M., Demaine, E., Eppstein, D., & Hayes, B. "A disk-packing algorithm for an origami magic trick." *International Conference on Fun with Algorithms.* June. 1998. (Citeseer PDF download)

Here is their paragraph on complexity (the algorithm is based on disk-packing):

For

*local feature size*, see

the Wikipedia article.
I doubt there could be a complexity bound in terms of $n$, the number of line
segments in the drawing to be folded and cut;
rather, it must depend on the geometry, as does the local feature size.

Q3: One can state a higher-dimensional analog, but no one has proven any result in three or higher dimensions. $\endgroup$ – Joseph O'Rourke Sep 24 '13 at 16:17