Well here is my working test... It's sloppy and inaccurate code, but eyy it works. So, I got it working, now time for optimizations.

Heres is the snippet though.
(Note the yaw value is 180f more than it is supposed to be, so 360* is now 540f hence the -180f)
        Vector3f collPos = didCollideTerrain();
        if (collPos != null) {
            if (game.getInputManager().isKeyDown(InputManager.KEY_W)) {
                setPosition(new Vector3f(
                        oldPos.getX(),
                        oldPos.getY(),
                        oldPos.getZ()));
                float oldYaw = yaw;
                /*
                 * x
                 */
                yaw -= 180f;
                if (yaw > 90f && yaw < 180f) {
                    yaw = xplus;
                } else {
                    if (yaw > 0 && yaw < 90f) {
                        yaw = xplus;
                    } else {
                        yaw = xminus;
                    }
                }
                moveForward(0.01f);
                if (didCollideTerrain() != null) {
                    moveBackward(0.01f);
                    yaw = oldYaw;
                    /**
                     * z
                     */
                    yaw -= 180f;
                    if (yaw > 0 && yaw < 90f) {
                        yaw = zminus;
                    } else {
                        if (yaw > 270 && yaw < 360) {
                            yaw = zminus;
                        } else {
                            yaw = zplus;
                        }
                    }
                    moveForward(0.01f);
                    if (didCollideTerrain() != null) {
                        setPosition(new Vector3f(
                                oldPos.getX(),
                                oldPos.getY(),
                                oldPos.getZ()));
                    }
                }
                yaw = oldYaw;
            } else {
                setPosition(new Vector3f(
                        oldPos.getX(),
                        oldPos.getY(),
                        oldPos.getZ()));
            }
            while (didCollideTerrain() != null) {
                moveBackward(0.05f);
                addY(0.01f);
            }
        }
I was just wondering if I could get some hints and tips about wall strafing, and collision detection in general. At the moment I am using basic boundary boxes.

I was just wondering if I could get some hints and tips about wall strafing, and collision detection in general.

This is actually the HARDEST part of 3D game programming for me. For some reason, the math and physics of it all makes my head spin after a while. It starts simple, with something like AABB or simple sphere collisions, paired with penetration measurements so you can backup/strafe/slide the moving object appropriately. Then you realize that you need to do "over-time" collision detection to prevent rare, yet occasional warping through objects. Mix that with the eventual "need" to do more bounding shapes; adding complex and convex hulls and the like. It turns into a huge mess for those of us not blessed with grade A minds.

Anyway, because of that death spiral, my recommendation is to find the absolute easiest collision detection and response system that you can get away with. If you're in 3D, start with spheres OR AABB, but not both. ONLY go further if you absolutely HAVE to. Also, consider using something prebuilt (like jBullet) if you want something more advanced (don't try to reinvent the wheel on this one).

Also, looking at your code, you probably don't want to be calling the "didCollideTerrain()" method multiple times (I'm assuming that's where your math is for detecting the collision). Try to setup a method that both detects and returns all of the variables you need to respond to the collision. Loop through your collidable objects once to gather the data, then loop through once more for the response. Also, don't just set your object to it's previous position; rather, create a reverse vector built off of how far your "player" has penetrated into the other object.

Phew... is that enough for now? 

I'd also recommend looking into some books. Something like Brackeen's "Developing Games in Java" or for something to really make your head pop, Ericson's "Real-time Collision Detection."

Thank you elias, quite the bunch of useful information there. Knowing myself I would have tried to reinvent the wheel, and probably sit on my computer for several days straight (exluding sleep and other stuff though).
I really don't like using libraries, it makes me feel powerless for some reason.

And thoose books, looks like they are going to be quite useful
But the walls strafing is still puzzling my head.

Wall strafing is determined by creating a backwards vector opposite the penetration vector... you back up only as far as the penetration and then move along the wall's vector for the remainder.  There's a whole section in the book I recommended about this exact topic (The "Developing Games in Java" book); I highly recommend reading it for more info. I'm afraid I can't be much more precise than that because so much matters on how your engine is setup.

And why didn't I think of that earlier.... You just solved the puzzle -.-