Here's an explicit example. The polynomial $f=x^{4} y^{2}+x^{2} y^{4}-x^{2} y^{2}+1$ is not a sum of squares (as one can check using Motzkin's original proof or by computer). On the other hand, the polynomial $f^3$ can be written as a sum of squares,
$$f^3=c_1F_1^2+c_2F_2^2+\ldots+c_{19}F_{19}^2$$ where the coefficients $c_i$ and polynomials $F_i$ are listed below.

I guess I should mention the software I used for computing this, namely the package "SOS.m2" for Macaulay2. This package has a function 'getSOS' which spits out a sum of squares representation of a given polynomial. See this link for details. The point is that the problem of finding such a representation can be viewed as a problem of semi-definite programming, and can be solved in reasonable time if the degree is small. In particular, this gives the algorithm you mention for checking whether a polynomial is non-negative.

EDIT: If anyone is interested, I have uploaded the Macaulay2 code here.

Now for the coefficients $c_i$:

```
(c1..c19)=(146/17,146/17,146/17,4036391/1186250,4036391/1186250,4036391/1186250,
74/25,1847624417319/1971413728310,431999528319079/461906104329750,
1847624417319/1971413728310,1847624417319/1971413728310,431999528319079/
461906104329750,431999528319079/461906104329750,8243/10693,1032024/
1393067,16675964223443/35265267617884,16675964223443/35265267617884,
389070/559013,16675964223443/35265267617884)
```

And the polynomials $F_i$:

```
(F_1,...,F_19)=(-459/3650 x^4 y^4-1071/3796 x^4 y^2-1071/3796 x^2
y^4+x^2 y^2-17/73,-17/73 x^6 y^3-1071/3796 x^4 y^5+x^4
y^3-459/3650 x^2 y^3-1071/3796 x^2 y,-1071/3796 x^5 y^4-17/73
x^3 y^6+x^3 y^4-459/3650 x^3 y^2-1071/3796 x
y^2,-65670975/137237294 x^5 y^4+8569925/68618647 x^3 y^6+x^3
y^2-65670975/137237294 x y^2,8569925/68618647 x^6
y^3-65670975/137237294 x^4 y^5+x^2 y^3-65670975/137237294 x^2
y,x^4 y^4-65670975/137237294 x^4 y^2-65670975/137237294 x^2
y^4+8569925/68618647,-175/629 x^5 y^3-175/629 x^3 y^5+x^3
y^3-175/629 x y,x^4 y^2-421805182124/9238122086595 x^2
y^4-80070895463/1231749611546,x^2
y^4-1201063431945/17632633808942,-80070895463/1231749611546 x^6
y^3-421805182124/9238122086595 x^4 y^5+x^2
y,-421805182124/9238122086595 x^5 y^4-80070895463/1231749611546 x^3
y^6+x y^2,x^5 y^4-1201063431945/17632633808942 x^3
y^6,-1201063431945/17632633808942 x^6 y^3+x^4 y^5,-21157/107159
x^5 y^3-21157/107159 x^3 y^5+x y,-21157/86002 x^5 y^3+x^3
y^5,x^6 y^3,1,x^5 y^3,x^3 y^6)
```