Let $(P, <)$ be a dense totally ordered set. Then there exists a complete totally ordered set $(C, \prec)$, such that:
Also $(C, \prec)$ is unique up to an isomorphism over $P$.
I understand how to prove existence of the completion $(C, \prec)$ via the Dedekind cuts construction, but I don't know how to prove uniqueness up to an isomorphism over $P$.
On
You mentioned Dedekind's completion of $P$. We can write it explicitly as $C=\{A\subseteq P\mid A\text{ is a proper, non-empty initial segment of }P\}$ ordered by inclusion, and $p\mapsto\{q\in P\mid q<p\}$ is the canonical embedding of $P$ into $C$.
Now suppose that $C'$ is another complete order with $P$ dense in $C'$, simply consider the map $\pi(c)=\{p\in P\mid p\prec_{C'}c\}$. And show that this is an isomorphism between $C$ and $C'$. Use the density of $P$ in $C$ and $C'$ for this.
This makes a slightly easier strategy than working with two abstract copies of an idea. Once you constructed one order like this, simply show that any other order is isomorphic to it.
Let $(C,\prec)$, $(C',\prec')$ be complete totally ordered sets s.t. 1-3 hold. Consider
$$ f \colon C \rightarrow C', \ c \mapsto \sup \{p \in P \mid p \prec c \}, $$ where the $\sup$ is calculated in $(C',\prec')$. (If $c$ is the least element in $(C,\prec)$, let $f(c)$ be the least element in $(C',\prec')$ and similar for maximal elements. Note that the density of $P$ guarantees that this goes through in every possible case.)
$f$ certainly respects the two orderings.
$f$ is injective: Given $c \prec d$ in $C$ fix $p \in P$ s.t. $c \prec p \prec q \prec d$. Then $f(c) \preceq' p \prec' q \preceq' f(d)$.
$f$ is surjective: Let $c' \in C'$. If $c'$ is the least element of $(C', \prec')$, there is nothing to do. Otherwise, as $P$ is dense in $C'$, we may write $c' = \sup X$ for some $X \subseteq P$ (calculated in $(C', \prec')$). Let $c := \sup X$ (calculated in $(C, \prec)$. Then by construction $f(c) = c'$.
This shows, that $f$ is the desired isomorphism.