How have you dealt with the lack of constructors in VB6?

How about using the available class initializer? This behaves like a parameterless constructor:

Private Sub Class_Initialize()
    ' do initialization here

End Sub

I use a mix of factory functions (in parent classes) that then create an instance of the object and call a Friend Init() method.

Class CObjects:

Public Function Add(ByVal Param1 As String, ByVal Param2 As Long) As CObject
  Dim Obj As CObject
  Set Obj = New CObject
  Obj.Init Param1, Param2
  Set Add = Obj
End Function

Class CObject:

Friend Sub Init(ByVal Param1 As String, ByVal Param2 As Long)
  If Param1 = "" Then Err.Raise 123, , "Param1 not set"
  If Param2 < 0 Or Param2 > 15 Then Err.Raise 124, , "Param2 out of range"

  'Init object state here
End Sub

I know the Friend scope won't have any effect in the project, but it acts as a warning that this is for internal use only. If these objects are exposed via COM then the Init method can't be called, and setting the class to PublicNotCreatable stops it being created.

I usually stick to factory methods, where I put the "constructors" for related classes in the same module (.BAS extension). Sadly, this is far from optimal since you can't really limit access to the normal object creation in VB6 - you just have to make a point of only creating your objects through the factory.

What makes it worse is having to jump between the actual object and your factory method, since organization in the IDE itself is cumbersome at best.