Short Answer: Jesus was going to baptize people with the Holy Spirit. This cleansing, purifying, regenerating work of the Holy Spirit in a person's life is referred to in a number of ways throughout Scripture, including baptism with the Holy Spirit and fire.
What Jesus came to do: Jesus' mission was to go to the cross, die, rise from the dead, and return to the Father. Jesus refers to this as His "baptism".
Why He did it: Before Christ came, all of humanity was spiritually dead. Christ came so that we could have life. It is the Spirit who gives life, but the Spirit could not come until Christ's work was complete. The purpose of Christ's mission was to enable the Spirit to enter into people's lives and then to "baptize" them into Christ, by the Spirit.
How we come to be "in Christ": Christ's followers are also called to be baptized -- that is, to go to the cross, die, rise from the dead, and return to the Father. (Note: This has both a spiritual sense for us today, and an ultimate sense at the end of the age.) All of this together can be referred to as "spiritual regeneration."
The language of regeneration: Spiritual regeneration is referred to throughout Scripture using a variety of terms, including death, crucifixion, circumcision, baptism, cleansing, purification, new birth, new creation, and new life. Why so much imagery? The whole point of Scripture is to describe spiritual realities, but human language is built on references -- mostly natural references. Since we are so natural-minded, and most of our words refer to natural things, it is necessary to use natural imagery to describe spiritual things.
Baptism: "Baptism in the Holy Spirit" refers to the spiritual regeneration that takes place when you are reconciled to God in Christ, by the Spirit. (This happened first at Pentecost.) Baptism is a really good picture for spiritual regeneration because it covers the "burial" of the old self, the cleansing that takes place by the Spirit, and being "raised up" all new and clean and fresh.
Fire: It is true that fire is sometimes used to signify judgment for the wicked, but it is also used throughout Scripture to signify purification. The term pairs up quite well with the term "baptism" because both are often used to signify purification and removal of uncleanness.
Baptism with the Holy Spirit and fire: There is one baptism, and there is only one baptism being described in this verse. "Holy Spirit" and "fire" are not presented as separate ideas in the Greek; they are presented as complimentary terms. It is pretty common in Scripture to find places where two terms are used together to paint a single image. (For example, Jesus refers to being born again as being born of water and Spirit [or wind], where water was a common symbol for the Spirit throughout Scripture.)
Trials? Fire is an appropriate image to use when describing the trials of life, since those who are in Christ are purified through trials. The verse in question is referring to baptism, though, so if we were going to make a connection to trials it would have to be an extension of the baptism in the Spirit and its connotations in the Christian life. In other words, this may be a valid implication of the interpretation, but I think it is an insufficient interpretation.
Judgment? Fire is an appropriate image to use when describing judgment, since fire burns up chaff, etc. But again, the verse in question is referring to baptism, and baptism signifies not only "death", but also cleansing, and new life. I suppose someone could try to argue that mankind on the whole will be "baptized" and the unclean will be removed (i.e. judged), thereby purifying mankind for relationship with God corporately. However, then suddenly the target audience of Luke 3:16 gets a bit confusing... is He also telling mankind they will be baptized with the Spirit? Also, this interpretation misses the presentation in the Greek of two complimentary terms.