That Paul says that the crossing of the sea is a “baptism” is surprising enough; but then he says that the baptism is “into the cloud.”  Where’d he get that?

You can suss that out from the exodus story, but I suspect that Paul has conflated the exodus story with the procedures for sacrifice.  Leviticus 1:9 says that the legs and entrails of an ascension offering are first “washed with water” and then “turned to smoke.”  The washing is immediately followed by a transfiguration into cloud.  Sacrificial animals were literally “baptized into the cloud.”

So also are we: Baptized into the cloud of witnesses that surrounds the throne, baptized into the company of angels that constitutes the glory of God, baptized into the cloud that is the Spirit-presence of the Son, baptized into sacrificial ministry, baptized to ascend, clothed in smoke and fire, into the Lord’s presence.