Methods and apparatus related to packet fragmentation and reconstruction are described. A sequence of bits is generated including at least one header and at least partial packet payload prior to a determination of the actual data rate to be used in a communications segment. In some embodiments, the generated sequence of bits corresponds to a prepared information bit stream for a best case scenario in which the highest data rate is selected for segment. Various embodiments allow for the selection of the data rate to be used for the communications segment to be delayed until just prior to the transmission. Thus the selection of the data rate for the communications segment, and thus the segment capacity, can be based on more current channel condition information than would otherwise be possible if the communications device needed to know the data rate for the segment before performing header and packet fragmentation operations.