Great question. I will answer it using t-SNE because I assume it is familiar to more people. I think UMAP is very promising and is a great contribution but to be honest I am getting a little bit annoyed with all the marketing and the hype that surrounds it. People think that t-SNE cannot embed new points but UMAP miraculously can. In reality, t-SNE can do it just as well as UMAP can; it is just a matter of convenient implementation.
A figure to attract attention:
they are non-parametric, i.e. there is no easy straightforward way to embed new data
This is not quite correct. It is true that t-SNE is non-parametric. What this actually means is that t-SNE does not construct a function $f(x):\mathbb R^p\to \mathbb R^2$ that would map high-dimensional points $x$ down to 2D. Instead it positions all the points on a plane and lets them "interact": similar points attract each other and dissimilar points repel each other, and after a while similar points gather together in clusters. In practical implementations, each point only feels attraction from its nearest $k$ neighbours for some small value of $k$.
Now imagine you get a new point $x_\mathrm{test}$. There is no function $f()$ that would give you its 2D position as $f(x_\mathrm{test})$. However, you can put it somewhere in the existing t-SNE embedding and let it "interact" with all existing points: it will be attracted to the points most similar to it (its nearest neighbours) and repeled from all other points. Only this point is allowed to move, while all existing points remain in place. If everything works well, $x_\mathrm{test}$ will arrive to its place somewhere close to its nearest neighbours.
When actually doing it, it is very helpful to position it initially somewhere close to its nearest neighbours (e.g. mean location of its $k$ nearest neighbours), because this will make the convergence much faster and much more reliable. In fact, simply positioning it at the mean location of its $k$ nearest neighbours can already work so well that no further optimisation would be needed at all.
[As an aside: if one has a whole bunch of test points, then one can deal with them independently one by one, or try to embed them all together and let them interact between each other as well. This can have very different outcomes if all test points are similar to each other but dissimilar to the original points. In the former case the test points will be "forced" into the existing embedding. In the latter case they will gather together as a separate cluster.]
I know several biology papers that used some variation of this method. Berman 2014 and Macosko 2015 are two such examples. Here is a very nice and very fast recent Python implementation of t-SNE https://github.com/pavlin-policar/openTSNE that allows embedding of new points out of the box. To quote the documentation https://opentsne.readthedocs.io/en/latest/,
[t-SNE has had several criticisms over the years, one of which is that] t-SNE is nonparametric therefore it is impossible to add new samples to an existing embedding. This argument is often repeated and likely comes from the fact that most software packages simply did not take the time to implement this functionality. t-SNE is nonparametric meaning that it does not learn a function $f$ that projects samples from the ambient space into the embedding space. However, the objective function of t-SNE is well defined and new samples can easily be added into an existing embedding by taking a data point and optimizing its position with respect to the existing embedding. This is the only available implementation we know of that allows adding new points to an existing embedding.
The figure above is from https://github.com/berenslab/rna-seq-tsne/ which is a companion repository to this paper: https://www.nature.com/articles/s41467-019-13056-x.
Regarding UMAP, as you say, the math behind the test set embeddings is not explicitly described anywhere, but I am quite sure that this is what it does. Briefly looking at the source code seems to confirm it.
