I've been trying to rotate my 3D objects to face the direction of a normalized vector, and I've gotten stuck with odd results. Could anyone give me some ideas on how to do this correctly? Also, one solution I've seen involves supplying an 'up' vector, which means the object can't point in the direction of that vector.

There are multiple ways the problem can be solved, and which will be most appropriate will generally depend on the circumstances.

Can you describe the context? What does the object represent? And what type of end behavior are you wanting to implement? (E.g. billboarding, adjusting orientation for steering behaviors, etc.).

Like jyk said it would be useful to know the context. Also, are you using matrices, and if so, which ones are available to you?

[font=arial, verdana, tahoma, sans-serif][size=2]I'm using 4x4 matrices to do all of my transformations with OpenGL 2.0+ (supports ES 2.0 as well). I use my own software transformation pipeline to get the vertices to their final position on the screen from object space.

These "objects" I am describing can be anything from 3D objects instantiated from loaded 3D models to cameras, lights, or particle emitters. I'm not concerned with steering my objects. I'm assuming that <0.0f, 1.0f, 0.0f> is my "up" vector, so I'd like all objects in 3D space to point in the direction of a normalized vector. The object should be rotated similar to how an FPS camera would work: the objects can rotate left and right around it's Y-axis (up vector), and also point up and down similar to aiming up and down. The object's Z vector should be ignored in rotations (no tilting involved).[/font]

One way that doesn't need an UP vector is to create a Change Of Basis transform matrix.
I discovered these in 'collision response with friction' as the solution I investigated involved transforming to and from 'contact space', defined only by a point and normal.
In those examples, the X axis was chosen to be the one that points somewhere, but I think that was totally arbitrary...

To make a change of basis transform matrix, we set one of the primary axes to be the desired direction (X,Y,Z).
We set another to be (-Y,X,Z), which is an orthogonal axis - just chosen one by convention.
We can set the third one as the crossproduct of the other two.
The result is a useful 3x3 rotation matrix which will rotate us such that the desired direction vector equals the chosen direction axis.

Rotating a direction vector into the direction of another vector doesn't need a supplementing axis at all; the both vectors are sufficient. Rolling a direction vector (i.e. rotating it about its own direction) has no effect on the vector. But doing the same rolling with an general shape has an effect. Hence you need another condition besides the 2 direction vectors just to complete the requirements. That is (in this case) a vector non-colinear to the computed (here forward) vector. Whether one choses the up or the side vector is mainly irrelevant for the principle.

[font="arial, verdana, tahoma, sans-serif"]I'm using 4x4 matrices to do all of my transformations with OpenGL 2.0+ (supports ES 2.0 as well). I use my own software transformation pipeline to get the vertices to their final position on the screen from object space.

These "objects" I am describing can be anything from 3D objects instantiated from loaded 3D models to cameras, lights, or particle emitters. I'm not concerned with steering my objects. I'm assuming that <0.0f, 1.0f, 0.0f> is my "up" vector, so I'd like all objects in 3D space to point in the direction of a normalized vector. The object should be rotated similar to how an FPS camera would work: the objects can rotate left and right around it's Y-axis (up vector), and also point up and down similar to aiming up and down. The object's Z vector should be ignored in rotations (no tilting involved).[/font]

What you describe is usually solved by constructing a basis from the given forward vector and an approximate up vector, using the basis as rotation matrix, and extending it with the position (more or less as mentioned by __Homer__).

[size=2][font=arial, verdana, tahoma, sans-serif][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]

One way that doesn't need an UP vector is to create a Change Of Basis transform matrix.
I discovered these in 'collision response with friction' as the solution I investigated involved transforming to and from 'contact space', defined only by a point and normal.
In those examples, the X axis was chosen to be the one that points somewhere, but I think that was totally arbitrary...

To make a change of basis transform matrix, we set one of the primary axes to be the desired direction (X,Y,Z).
We set another to be (-Y,X,Z), which is an orthogonal axis - just chosen one by convention.
We can set the third one as the crossproduct of the other two.
The result is a useful 3x3 rotation matrix which will rotate us such that the desired direction vector equals the chosen direction axis.

Rotating a direction vector into the direction of another vector doesn't need a supplementing axis at all; the both vectors are sufficient. Rolling a direction vector (i.e. rotating it about its own direction) has no effect on the vector. But doing the same rolling with an general shape has an effect. Hence you need another condition besides the 2 direction vectors just to complete the requirements. That is (in this case) a vector non-colinear to the computed (here forward) vector. Whether one choses the up or the side vector is mainly irrelevant for the principle.[/font][/font][font="arial, verdana, tahoma, sans-serif"][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]
[/font][/font][font="arial, verdana, tahoma, sans-serif"][size=2][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"][/font][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]In the example above the supplementary vector is chosen as [ -y x z ][sup]t[/sup] where [ x y z ][sup]t[/sup] is the desired forward vector. The dot-product of the vectors is z[sup]2[/sup], so that it is a valid supplementary vector if and only if the forward vector isn't [ 0 0 1 ][sup]t[/sup]. This is a requirement similar to [/font][size=2][size=2]the forward vector not pointing along the cardinal y direction [size=2][size=2]if using [ 0 1 0 ][sup]t[/sup] as approximate (up) vector.

[size=2][size=2]In summary, I'm not quite sure what you mean with "[/font][size=2]doesn't need an UP vector"[size=2]. Could you please elaborate?[/font][font=arial, verdana, tahoma, sans-serif][size=2][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]
[/font][/font][font=arial, verdana, tahoma, sans-serif][size=2][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]
[/font][/font][font=arial, verdana, tahoma, sans-serif][size=2][size=2][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2]

[/font][font="arial, verdana, tahoma, sans-serif"][size=2][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2][size=2][size=2]I'm using 4x4 matrices to do all of my transformations with OpenGL 2.0+ (supports ES 2.0 as well). I use my own software transformation pipeline to get the vertices to their final position on the screen from object space.[/font][/font][/font][font=arial, verdana, tahoma, sans-serif][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2][font="arial, verdana, tahoma, sans-serif"][size=2][size=2][size=2][size=2]
These "objects" I am describing can be anything from 3D objects instantiated from loaded 3D models to cameras, lights, or particle emitters. I'm not concerned with steering my objects. I'm assuming that <0.0f, 1.0f, 0.0f> is my "up" vector, so I'd like all objects in 3D space to point in the direction of a normalized vector. The object should be rotated similar to how an FPS camera would work: the objects can rotate left and right around it's Y-axis (up vector), and also point up and down similar to aiming up and down. The object's Z vector should be ignored in rotations (no tilting involved).[/font]

What you describe is usually solved by constructing a basis from the given forward vector and an approximate up vector, using the basis as rotation matrix, and extending it with the position (more or less as mentioned above).[/font][/font][/font]