Lots of things have to come together. First, how do you know what the stock price is, recent trades, their volumes, etc? Well, thankfully, you live at the turn of the century, so ticker tape exists. American Telegraph Company, the predecessor of Western Union, invented ticker tape, which used telegraph wires to transmit stock information, usually just the ticker, price, and volume, over long distances. This, along with newspapers like the Wall Street Journal, would help you stay on top of the movements of the market.

But what if you want to make a trade? You'd almost definitely need a broker in New York because the market would have been much more illiquid back then (various things help to explain the current liquidity in the market, but technological progress is one of the biggest reasons; for a recent example, HFTs help bring liquidity to the market as they trade large amounts of diversified stocks very often). This illiquidity meant that if you wanted to buy or sell stock, it might have been difficult to find someone to sell it to or buy from. Your broker would help you do so, for a fee (modern platforms like E-Trade are cheap because of market liquidity).

But how does the broker match buyers and sellers? Well, he is probably part of a firm that has people on the floor of the stock exchange, where they actually exchanged stocks. All those people yelling, the frantic hand signals, etc. all used to be extremely important as people needed to find buyers and sellers to complete their trades. Your broker might have also been able to work behind the scenes with other brokers in order to avoid the floor or even within his own firm if he found a match.

Thus, you would know about the market with the help of the telegraph and ticker tape, would presumably communicate with your broker via telegraph, and your broker would execute the trade most likely by having people on the floor of the exchange complete the trade or by working with other brokers or within his own firm.

Finally, as with any trade, the price is never constant. Even the buyers and sellers have different initial prices, the bid vs. the ask. You would probably tell your broker what volume you wanted to trade and at what price (or within what range). He would do his best execute the trade without crossing the spread in order to maximize your (and his) profit.

Even earlier in history, it would have been harder to invest in stocks. For example, in the late 18th century, you would probably have to meet with traders on Wall Street under the famous buttonwood tree in order to execute a trade.

Reference:

The Stock Market, Teweles

Since some people have already discussed the American aspect, I'll bring up instead the Amsterdam exchange of shares of the Dutch East India company, which is one of the earlier speculations of direct shares in a company, as discussed in Josseph de la Vega's Confusion of Confusions. The trade here was derived from the abundant commodity and goods trading that occurred in the Netherlands due to its sound logistical location allowing for river trade and ocean trade, as well as the resulting warehouses and trading facilities that made such trade possible.

Depending on the type of investor/speculator, buying and selling stock could be rather haphazard. You had everything from direct sales with immediate payment (the most traditional way of buying and selling stocks) to things like using stock as collateral (up to 4/5ths), the trading of options (calls and puts) as well as other derivatives: and you even had an attempt to short sell the bonds (which ended poorly when the company board, to prevent the stock from losing value, banned short sales, not that this stopped people from doing so anyways). These sales were typically executed through one of many self-styled brokers. There were two types of brokers-those designated by the company and "free brokers" that were not designated as such but were surprisingly trustworthy in that regard. Often times brokers would ally with other brokers that shared similar outlooks on if they felt the price would go up or down.

Re: locations, in the case of Amsterdam, trading efforts primarily focused around a certain public place, which changed over time (for instance from a commonly traversed bridge to a church square, etc.) although there was also an official Exchange building where trades were conducted. Trading could also be done in coffee houses, or even in bed, so long as a contract was drafted up and agreed to. Alternatively there were other cities where shares were being sold: while Amsterdam dominated the trade, other Netherlands cities also traded the shares, often at different prices than those in Amsterdam.

Once the terms of the trade were agreed upon by the brokers and customers, the actual execution and settlement needed to take place. A company representative would announce the end of trading for the day by waving a signal (which some people wanted sooner and some later) and the price for the day was decided upon relying on the advice of two "respected individuals."

On settlement day, the trade was typically executed on the basis of a "difference." Namely, the investors would agree to buy and sell stock at a certain price, and then on settlement date the transaction would go through with the difference between the market price and the agreed upon price exchanging hands between the speculator that had guessed "right" and the one that had guessed "wrong." There was certainly a gambling element to this sort of speculation. Trading was assisted by the Bank of Amsterdam, which helped to settle accounts of speculators (done monthly), allowing a speculator to potentially cancel out several of his transactions if he chose (i.e. buying a put as a hedge for a long trade).

Overall, there was very little security, strict rules, or general enforcement outside of the conditions of the market. The propensity for swindling was enormous, but many speculators grew accustomed to these tricks and developed independent countermeasures. They formed alliances and cliques depending on their efforts: at one point the "Portuguese" Jewish community was accused of attempting to rig the market, but other speculators-the predecessors of today's "research analysts" if you will-criticized the accuser's arguments. Of course, rumormongering was also a persistent threat, much like it is in today's markets. While the technology may certainly be nowhere that of today's markets, many institutions and procedures used today are thus derived from those markets many years ago.