Suppose you have a 2-dimensional polyhedral surface with specified lengths for the edges so that the vertices all have positive curvature. I believe this has a unique isometric embedding into 3-dimensional Euclidean space as the boundary of a convex polyhedron. Could someone confirm this? If so, is there a reasonable algorithm for finding the isometric embedding computationally?
Yes, this is the historically first version of the Alexandrov embedding theorem which was earlier discussed here. See the original Alexandrov's monograph (reviewed here), or see my book if you like downloadable stuff (at least for now).
The algorithmic issue is difficult. If you want the usual complexity, in my paper with Fedorchuk we showed that this requires finding roots of polynomials with exponential degrees. The practical algorithm (based on a new completely different proof of the Alexandrov theorem) was found by Bobenko and Izmestiev here and further analyzed here.