We investigate numerically the propagation of self-trapped optical beams in nematic liquid crystals. Our analysis includes both spatial and temporal behavior. We display the formation of stable solitons in a narrow threshold region of beam intensities for fixed birefringence, and depict their spatiotemporal instabilities as the input intensity and the birefringence are increased. We demonstrate the breathing and filamentation of solitons above the threshold with increasing input intensity, and discover a convective instability with increasing birefringence. We consider the propagation of complex beam structures in nematic liquid crystals, such as dipoles, beam arrays, and vortices.