This is a famous problem, sometimes called the coin problem of Frobenius.
If $n=2$ the answer to your question is known to be $N = t_1 t_2 - (t_1 + t_2) + 1$. A proof of this can be found in the answer to this recent question.
For three or more integers, there is no known closed-form solution for $N$. There are some bounds on the values of $N$ in the $n = 3$ case, as well as some algorithms for determining $N$. For more information and references, see the Wikipedia and MathWorld pages on the Frobenius coin problem.
Basically, the problem is considered solved when $n = 2$, partially solved (because of the bounds and algorithms) when $n = 3$, and unsolved when $n \geq 4$.
Update: Guy's Unsolved Problems in Number Theory says, "The case $n = 3$ was first solved explicitly by Selmer and Beyer, using a continued fraction algorithm." So I guess the $n=3$ case has been solved. I suppose you have would have to dig up their paper (it's in the MathWorld references) to see their solution.
I realized the answer soon after writing the question. Since the site explicitly encourages people answering their own question, I figured I would write it up.
First, notice that if $x_1,\dots,x_k$ are independent uniform from $[0,1]$, then $\max\{x_1,\dots,x_k\}$ has the same distribution as $x^{1/k}$ where $x$ is uniform in $[0,1]$. To prove this, note that for any $c\in[0,1]$,
\begin{array}{c}
P(\max\{x_1,\dots,x_k\}\le c)=\prod_{i=1}^k P(x_i\le c)=c^k\\
P(x^{1/k}\le c)=P(x\le c^k)=c^k
\end{array}
Thus the cdfs agree and therefore so do the distributions.
Therefore, our question is equivalent to proving that
\begin{align*}
P\big(&\max\{x_{1,1},\dots,x_{1,k_1}\}+\max\{x_{2,1},\dots,x_{2,k_2}\}+{}\dotsb\\
&{}+\max\{x_{n,1},\dots,x_{n,k_n}\}\le1\big)=\frac{k_1!k_2!\dotsm k_n!}{(k_1+k_2+\dotsb+k_n)!}
\end{align*}
for $k_1+k_2+\dotsb+k_n$ independent uniform variables $x_{1,1},\dots,x_{n,k_n}$.
On the other hand, we can work backwards from the solution. Suppose again we choose $k_1+k_2+\dotsb+k_n$ independent uniform variables $x_{1,1},\dots,x_{n,k_n}$, as above. Then the probability that all $x_{1,i}$ are less than all $x_{2,i}$, which are less than all $x_{3,i}$, etc., is also $\frac{k_1!k_2!\dotsm k_n!}{(k_1+k_2+\dotsb+k_n)!}$. This is because there are $k_1!k_2!\dotsm k_n!$ ways to permute the variables under this restriction, and $(k_1+k_2+\dotsb+k_n)!$ permutations total.
Let's use vector notation as a sort of shorthand. Let $\max\vec v$ mean the maximum coordinate of $\vec v$, and let $\vec u\le\vec v$ mean that every coordinate of $\vec u$ is less than every coordinate of $\vec v$. Then
$$A=\{\vec{\mathbf x}\in[0,1]^{k_1}\dotsm[0,1]^{k_n}:\max\vec x_1+\dotsb+\max\vec x_n\le1\}$$
is the set on which the procedure in the first section succeeds, and
$$B=\{\vec{\mathbf x}\in[0,1]^{k_1}\dotsm[0,1]^{k_n}:\vec x_1\le\dotsb\le\vec x_n\}$$
is the set on which the second set succeeds. (It's worth noting here that $\binom{k_1+\dotsb+k_n}{k_1,\dots,k_n}$ congruent copies of $B$ fill up $[0,1]^{k_1+\dotsb+k_n}$, from permuting the coordinates.) We wish to show that $\operatorname{Vol}(A)=\operatorname{Vol}(B)$. I claim that I can transform $B$ into $A$ by means of a bijective piecewise-linear transformation with determinant $1$ everywhere, finishing the proof.
Let $T:B\to A$ be the piecewise-linear transformation defined by taking every random variable of each group and subtracting the maximum value of the previous group. In vector shorthand, this is
$$T:(\vec x_1,\dots,\vec x_n)\mapsto(\vec x_1,\vec x_2-\max\vec x_1,\dots,\vec x_n-\max\vec x_{n-1}).$$
Expanding out the shorthand, this means
$$T:(\dots,x_{i,j},\dots)\mapsto(\dots,x_{i,j}-\max\{x_{i-1,1},\dots,x_{i-1,k_{i-1}}\},\dots).$$
By the definition of $B$, each coordinate maps into $[0,1]$. This is bijective since we can define $T^{-1}:A\to B$ by adding the maxima of all previous groups:
\begin{align*}
T^{-1}:(\vec x_1,\dots,\vec x_n)\mapsto(&\vec x_1,\vec x_2+\max\vec x_1,\dots,\\&\ \vec x_n+\max\vec x_{n-1}+\dotsb+\max\vec x_1).
\end{align*}
$T$ is piecewise linear since $\max$ is piecewise linear on its arguments. Except on a set of measure zero, at every point $\vec{\mathbf x}=(\vec x_1,\dots,\vec x_n)$, the transformation $T$ is a triangular matrix (exactly which matrix depends on the the maxima of each group in $\vec{\mathbf x}$), with $1$s on its diagonal; therefore, since $T$ is bijective, it preserves volume. Thus $\operatorname{Vol}(A)=\operatorname{Vol}(B)$ and the theorem is proved.
PS: A few hours after writing this, I found a second proof. Let $\Delta_k$ be
$\{(x_1,\dots,x_k)\in[0,1]^k:x_1+\dotsb+x_k\le1\}$. Then if we pick a point uniformly at random from within $\Delta_k$, then it can be shown from a geometric scaling argument that $x_1+\dotsb+x_k$ is distributed like $x^{1/k}$. Furthermore, it is well-known (and can be shown using similar logic to the above) that $\operatorname{Vol}(\Delta_k)=1/k!$. From there, the probability we want is simply
$$\frac{\operatorname{Vol}(\Delta_{k_1+\dotsb+k_n})}{\operatorname{Vol}(\Delta_{k_1}\times\dotsm\times\Delta_{k_n})}=\frac{1/(k_1+\dotsb+k_n)!}{1/k_1!\dotsm 1/k_n!}.$$
In my eyes the first proof is still more "combinatorial," but I thought I'd post this here too.
Best Answer
The claim is false for odd $p$. Indeed, in that case the probability that a sampled number is even is slightly larger than $\frac 12$, hence there is $c>\frac12$ depending only on $p$ such that the gcd is $1$ (or at least odd) at most with probability $\le 1-c^n$. For $n\gg 0$, we have $(2c)^n>p$ and then $1-c^n<1-p/2^n$.
For even $p$, the claim is true:
We solve the cases $p=2$ and $p=4$ manually:
$p=2$: The probability that all samples are even is $2^{-n}$, hence the gcd is $1$ with probability $1-2^{-n}\ge 1-p/2^n$.
$p=4$: All samples are even ($0$ or $2$) with $2^{-n}$ and all are multiples of $3$ ($0$ or $3$) with $2^{-n}$, and both conditions occur together with probability $4^{-n}$. Hence the gcd is $1$ with probability $1-2^{-n}-2^{-n}+4^{-n}>1-2/2^n>1-4/2^n$
From now on, let $p$ be even and $\ge 6$. Let $q$ be a prime $<p$. As there are $\lceil \frac{p-1}{q}\rceil<\frac pq+1$ multiples of $q$ in the range, the probability that a sampled number is a multiple of $q$, is $\le \frac 1q+\frac1p$. Let $X_q$ be the event that the gcd of the $n$ sampled numbers is a multiple of $q$. Then $$P(\gcd=1)=1-P(X_2\lor X_3\lor X_5\lor \ldots) $$ were we run over all primes $<p$ on the right. Now $$P(X_2\lor X_3\lor X_5\lor \ldots)\le P(X_2)+P(X_3)+P(X_5)+\ldots.$$ For $5\le q<p$, we have $\frac 1q+\frac1p<\frac 2q<\frac12$ and hence $P(X_q)<\frac1{2^n}$. For $q=3$, we have $\frac1q+\frac1p\le\frac13+\frac16=\frac12$ and hence $P(X_3)\le \frac1{2^n}$. Finally, as $p$ is even, we can compute $P(X_2)=2^{-n}$ exactly. As there are at most $\frac{p}2$ primes $\le p-1$, we arrive at the bound $$P(X_2\lor X_3\lor X_5\lor \ldots)\le \frac{p}2\frac1{2^n}$$ and thus $$P(\gcd=1)\ge 1-p/2^{n+1}>1-p/2^{n}. $$