First, I'd like to point out the problem doesn't have a classical solution, which should be $C^1$ continuous and satisfy all the i.c. and b.c. in the whole interested domain. This can be easily proven by finding the general solution of the equation:
{eq, ic, bc} = {D[u[x, t], x] == D[u[x, t], t], u[x, 0] == x^2, u[0, t] == t} generalsol = First@DSolve[eq, u, {x, t}] (* {u -> Function[{x, t}, C[1][t + x]]} *)
and substituting it to i.c. and b.c.:
{ic, bc} /. generalsol (* {C[1][x] == x^2, C[1][t] == t} *)
Clearly the only function relationship satisfying ic is Function[a, a^2], while the one satisfying bc is Function[a, a], so they can't be satisfied simultaneously, as long as we require the solution to be smooth.
Still, if we lower our requirement a bit i.e. allow solution that doesn't satisfy the equation and corresponding i.c. and b.c. in some region, we can find weak solution. (Well, to be honest I'm not sure if it's the correct terminology. I've asked it in Math.SE.)
One weak solution can be found by using Laplace transform on t (I'll use pdeSolveWithLaplaceTransform for the task):
(* Definition of pdeSolveWithLaplaceTransform isn't included in this post, please find it in the post above. *) asol[x_, t_] = pdeSolveWithLaplaceTransform[{eq, bc}, ic, u[x, t], t, x] (* (t + x)^2 + (t - t^2 + x - 2 t x - x^2) HeavisideTheta[t + x] *)
It's the same as given by DSolve, as shown in zhk's answer.
Notice this solution does not satisfy the original equation at $t+x=0$ (HeavisideTheta isn't defined at 0), ic when $x>0$ and bc when $t<0$:
Plot[Subtract @@ ic /. u -> asol // Evaluate, {x, -10, 10}]
This isn't the only possible weak solution, if we treat x as time i.e.:
asol2[x_, t_] = pdeSolveWithLaplaceTransform[{eq, ic}, bc, u[x, t], x, t] (* t + x - (t + x) HeavisideTheta[t + x] + (t + x)^2 HeavisideTheta[t + x] *)
This solution does not satisfy the original equation at $t+x=0$, ic when $x<0$ and bc when $t>0$.
As you see, when weak solution comes on stage, the problem doesn't have a unique solution. If neither of the 2 solutions above is the one you need, there must be a missing auxiliary conditions. As to auxiliary condition, here's an example:
Position of discontinuous coefficient influences the solution of PDE
Finally, I believe the reason why NDSolve has trouble in finding the numeric solution of the problem is, currently NDSolve doesn't have a strong enough support for weak solution problem. Here's just another few troublesome cases:
1D Euler equations (fluid dynamics) with NDSolve
Circumvent NDSolve::bdord: error for 1-D Euler Equations
Solving wave equation with singular initial conditions
