Is there a way to find any non-trivial $\mathbb{F}_p(t)$-point on the given elliptic curve? Consider a finite field $\mathbb{F}_p$ (where $p \equiv 1 \ (\mathrm{mod} \ 3)$, $p \equiv 3 \ (\mathrm{mod} \ 4)$) and the elliptic curve
$$
E\!:y^2 = x^3 + (t^6 + 1)^2
$$
over the univariate function field $\mathbb{F}_p(t)$.
Is there a way to explicitely find any $\mathbb{F}_p(t)$-point on $E$ outside $E[3]$ (i.e., $x \neq 0$)?
 A: If $2$ is a cube mod $p$ then you can take 
$(x,y) = (ct^2, t^6-1)$ where $c^3 = -4$.
This works for every odd $p \equiv -1 \bmod 3$,
but since you specified $p \equiv +1 \bmod 3$
the first case is $p=31$, with $c \in \{-3,-15,18\}$.
The next few such $p$ are $43, 127, 223, 283, 307, 439, 499, 643, 691$.
By Cubic Reciprocity, the condition on $p$ is equivalent to
$p = m^2 + 27 n^2$, and then your further requirement $p \equiv 3 \bmod 4$
is equivalent to $(m,n) \equiv (0,1) \bmod 2$, e.g. $(m,n)=(2,1)$ for $p=31$.
Ultimately this works because the "potentially constant" curve $E$
is the cubic twist of $E_0: y^2 = x^3 + 1$ by $u^3 = t^6 + 1$,
and the constant curve $E_0$ is isogenous with $x^3 + y^3 = 2$.
If it were the Fermat cubic $x^3 + y^3 = 1$ then you could always do it,
but to reach $x^3 + y^3 = 2$ you need a cube root of $2$.
A: You can observe that the elliptic curve $E_2: y^2=x^3+(t^3+1)^2$ is a generic fibre of a rational elliptic surface. Over the algebraically closed field $k$ the group of $k(t)$ points on the curve has rank equal to 2 (by the Shioda-Tate formula) and from the classification of possible groups of $k(t)$-rational points by Oguiso-Shioda (case 39 because we have three places of reduction type $IV$ away from characteristic 3) the group of $k(t)$-rational points modulo torsion has a lattice structure $A_2^{*}$. So we are looking at the points of height $1/2$ and this can be found only when one hits two singular points in the Weierstrass equation at places of bad reduction. So you obtain points of the form
$P_i=((4^{1/3}\cdot \zeta_3^i)(1 - t + t^2), \sqrt{-3}(-1 + t)(1 - t + t^2)$ for i=0,1,2
We have the relation $P_0+P_1+P_2=0$ and th points $P_1,P_2$ span a lattice of type $A_2^*$, hence are free generators.
Now you have to apply the map $t\mapsto t^2$ and on the elliptic curve $y^2=x^3+(t^6+1)^2$ you obtain two linearly independent points $P_1'$ and $P_2'$. Notice that $P_1'-P_2'$ is the negative of the point found by Noam Elkies.
The points are defined over $\overline{\mathbb{Q}}(t)$. By reduction they will become naturally points over $\overline{\mathbb{F}}_{p}(t)$ and can provide points defined over $\mathbb{F}_{p}(t)$.
With a trace formula and point count (which can be done in Magma as pointed out by Jeremy Rouse in his answer) you can check that in several characteristics the rank over $\mathbb{F}_{p}(t)$ can be higher than $2$. This follows from Tate conjecture and is unconditional because the given elliptic curve is a generic fibre of a K3 surface. For example: in characteristic $p=5,11,13,17$ the rank over $\mathbb{F}_{p}$ is equal to $4$.
Addendum:
One can play the same game with the elliptic curve $E_{tw}=E_{1}^{(t)}: y^2=x^3+(t+1)^2\cdot t^3$, which under the base change $t\mapsto t^6$ becomes isomorphic to the original curve. Curve $E_{tw}$ is a generic fibre of the rational elliptic surface with rank over $\overline{\mathbb{Q}}(t)$ equal to $2$ again (now the singular fibres have different reduction type: $I_{0}^{*}$, $II$ and $IV$.). This is the case $32$ in the Oguiso-Shioda table. We find the following points of required height
$Q_{i}=(\zeta_{6}^{i}(1+t)t, \sqrt{-1}t^2(1 + t))$
for $i=1,3,5$.
There is the equality $Q_{1}+Q_{3}+Q_{5}=0$ and the points $Q_{1}$ and $Q_{3}$ are lineary independent.
Now, we base change again to the elliptic curve $y^2=x^3+(t^6+1)^2$ and obtain the following set of four linearly independent points obtained via a base change
$$\{P_{1}',P_{2}', Q_{1}',Q_{3}'\}$$
The Gram matrix is a block matrix of determinant 4. 
Second addendum:
Finally, we consider a curve $F:y^2=x^3+(t^3-3t)^2$. It is isomorphic to $y^2=x^3+(t^6+1)^2$ under the pullback by $t\mapsto t+1/t$. Curve $F$ has three places bad reduction of type $IV$. Hence we find from the Oguiso-Shioda the points of height $1/2$. Those points are
$$R_{i}=(\zeta_{6}^{i}(t^2 - 3),\sqrt{3}(-3 + t^2))$$
for $i=1,3,5$.
We have $R_{1}+R_{3}+R_{5}$ is zero and we finally obtain the set of 6 linearly independent points
$$\{P_{1}',P_{2}', Q_{1}',Q_{3}',R_{1}',R_{3}'\}$$
which have a Gram matrix of determinant $4/3$. 
The calculations above for several characteristics show that we cannot have more than 6 independent points in the group $E(\overline{\mathbb{Q}}(t))$, so up to finite index we found a basis of points. From this using the Galois action on the points you can work out the exact value of the $\mathbb{F}_{p}(t)$ rank in the cases when the Tate conjecture computation matches this bound. For the primes where the rank over $\overline{\mathbb{F}}_{p}(t)$ is higher than $6$ the extra points might exist for very peculiar reasons, e.g. the Shioda-Inose structure might throw some extra divisors into the picture and the heights of those points can be very large.
A: This is too long for a comment, so I'm making it an answer. Magma now has machinery for computing ranks and generators over function fields (see here) which only work for rational elliptic surfaces (using the connection with the Neron-Severi group). I used the L-function machinery (see here) to compute the analytic ranks for $p = 7$, $p = 19$ and $p = 31$. One can in theory search for points the same way as one does for curves over number fields. When $p = 31$, the analytic rank is $2$ (and one generator can be found from Elkies's answer). Doing a 2-descent finds a 2-Selmer group of rank 8 (meaning there are 255 2-covers one could search for points on). The Cassels-Tate pairing is not yet implemented over function fields in Magma.
