These questions are really interesting; although seem simple, some are close to the very nature of the electromagnetic theory, which is very hard to explain. My answers are as follows:
How does an electric charge produce an electric field?
The electric 'field', is a virtue measure of the 'potentials' from the coulomb force. An analogy is one can define a 'gravity field' from earth, which can build up the potential energy of a ball on the table.
General idea is 'force leads to work, work leads to potential energy, and potential energy leads to field.' If you can find a source to provide constant force in any means, you may
also define a certain 'field' for it.
How is this field maintained over time without the input of energy?
First, if the electric-field does not interact with other charges so it does not incur positive or negative 'work', the field should remain. Much like a ball stand still on the table, and the 'gravity field' from the ball to Earth shall remain constant.
If the electric-field does incur positive work or negative work, then in general, the field may not maintain without input energy-unless the field source can be approximated as infinitely strong, and the work produced to the external charge are neglect-able.
When the charge moves, why is or isn't there any remnant of the field left behind in space?
Yes, there is remnant field left in space. The simplest understanding is also connecting field to force. If the charge moves (but still exists), the 'potential' of the coulomb force moves accordingly, and the electric field moves accordingly.
It is noteworthy that quantitatively describing charges in moving field is usually difficult or sometimes even impossible (unless the moving field is very regular, such as the periodic rotating field). In most of the cases we only study the field in 'steady states'.